Beta Round #66-C: LionAge II

keyword

動的計画法　C++

問題概要

長さL(<100)の文字列がある。隣合う文字に応じて得点が加減されていく。もとの文字列をK(<100)箇所まで書き換えてよい。得られる得点の最大値を求める問題。

解法

dp[i文字目][書き換えた回数][i文字目に何が入っているか]でDP。状態がL*K*26で、ひとつの状態から他の状態に配るのに26だから計算量はO(L*K*26^2)。dpの2つ目は"書き換えられる残り回数"とするより"書き換えた回数"の方が場合分けが減って楽だと思う。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int table[0x100][0x100];
int dp[109][109][26];
char str[209];
int K, N;
const int INF = 1<<29;

int solve(){
	N = strlen(str);
	for(int i=0; i<109; i++){
		for(int j=0; j<109; j++){
			for(int k=0; k<26; k++){
				dp[i][j][k] = -INF;
			}
		}
	}
	for(int i=0; i<26; i++){
		dp[0][i+'a'==str[0]?0:1][i] = 0;
	}
	for(int i=0; i<N-1; i++){
		for(int k=0; k<=K; k++){
			for(int j=0; j<26; j++)if(dp[i][k][j] != -INF){
				for(int a=0; a<26; a++){
					dp[i+1][str[i+1]-'a'==a?k:k+1][a] = max(dp[i+1][str[i+1]-'a'==a?k:k+1][a], dp[i][k][j] + table[j][a]);
				}
			}
		}
	}

	int ans = -INF;
	for(int k=0; k<=K; k++){
		for(int j=0; j<26; j++){
			ans = max(ans, dp[N-1][k][j]);
		}
	}

	return ans;
}

int main(){
	scanf("%s ",str);
	scanf("%d ",&K);
	int M;
	scanf("%d ",&M);
	for(int i=0; i<M; i++){
		char a, b;
		int d;
		scanf("%c %c %d ",&a,&b,&d);
		table[a-'a'][b-'a'] = d;
	}
	printf("%d\n",solve());
	return 0;
}