Codeforces 73C: LionAge II

Problem - C - Codeforces

Difficulty: 1800

問題概要

英小文字で構成される長さNの文字列Sと整数kが与えられる．連続する2文字にはスコアが存在し，文字列のスコアは，隣接する2文字のスコアの合計である．Sをk文字まで好きな文字に置き換えることが許されるとき，取りうる最大のスコアは何点か？

N <= 100

k <= 100

解法

次のようなDPを考える．

DP[n][z][k] := n番目までを考えて，最後の文字がzで総置換回数がk回以下のもののうち，最大スコア

最後の文字ごとに状態を分けることがミソ．DP[n][z][k]は，

1) S[n] == zのとき，DP[n-1][*][k] のうち最大

2) S[n] != zのとき，DP[n-1][*][k-1]のうち最大

で求められる．

int euph[26][26] = {};
int dp[110][26][110] = {}; // dp[n][z][k] := n番目までを考えて，最後の文字がzで総置換回数がk回以下のもののうち，最大euph

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    int len = S.length();
    int K; cin >> K;
    int N; cin >> N;
    REP(i,N){
        char a,b; cin >> a >> b;
        int c; cin >> c;
        euph[a-'a'][b-'a'] = c;
    }

    // 初期値セット
    REP(i,110) REP(j,26) REP(k,110) dp[i][j][k] = -INF;
    REP(i,26){
        REP(j,110){
            if(S[0]-'a' != i && j == 0){
                continue;
            }else{
                dp[0][i][j] = 0;
            }
        }
    }

    // 遷移
    for(int i = 1; i < len; i++){
        REP(j,26){
            REP(k,110){
                if(j == S[i]-'a'){
                    REP(l,26){
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][k] + euph[l][j]);
                    }
                }else{
                    if(k == 0) continue;
                    REP(l,26){
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][l][k-1] + euph[l][j]);
                    }
                }
            }
        }
    }
    int ans = -INF;
    REP(i,26){
        ans = max(ans,dp[len-1][i][K]);
    }
    cout << ans << endl;


}