Codeforces Beta #66 C. LionAge II - kusano

動的計画法。最後の文字と書き換え回数ごとに最大ボーナスを覚えておく。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string s; cin >> s;
    int k; cin >> k;
    int n; cin >> n;
    static int bonus[128][128];
    for ( int i=0; i<n; i++ )
    {
        char x, y;
        int c;
        cin >> x >> y >> c;
        bonus[x][y] = c;
    }

    //  [i][j][k]　iまでの位置でj回書き換えて最後の文字がkで得られる最大ボーナス
    static int T[128][128][128];
    for ( int i=0; i<128*128*128; i++ )
        T[0][0][i] = -99999999;
    for ( int x='a'; x<='z'; x++ )
        T[0][s[0]==x?0:1][x] = 0;

    for ( int i=1; i<(int)s.length(); i++ )
    for ( int j=0; j<=k; j++ )
    for ( char y='a'; y<='z'; y++ )
    for ( char x='a'; x<='z'; x++ )
    if ( y==s[i] || j>0 )
        T[i][j][y] = max( T[i][j][y], T[i-1][y==s[i]?j:j-1][x]+bonus[x][y] );

    int ans = -99999999;
    for ( int i=0; i<=k; i++ )
    for ( int x='a'; x<='z'; x++ )
        ans = max( ans, T[s.length()-1][i][x] );

    cout << ans << endl;
}