AtCoder AGC #021 : D - Reversed LCS

シンプルな問題設定でいいですね。
https://agc021.contest.atcoder.jp/tasks/agc021_d

問題

文字列Tの価値は、TとTを反転したもののLCSの長さとする。
文字列Sが与えられる。S中の文字列を最大K個任意の文字にできるとき、価値の最大値を求めよ。

解法

f(L,R,k) := S[L..R]とそれを反転した文字列について、最大k回文字の変更をできるときの価値の最大値
とする。
f(0,|S|-1),K)が求めたい値となる。

[L,R]の区間が小さい順に求めていこう。
まず初期状態として

• S[L,L,k] = 1
• S[L,(L+1),k] = S[L]==S[L-1]なら2、そうでないなら1

後者のケースを忘れやすいので注意。

以下区間長が3以上の時を愚直に考えればよい。

• S[(L-1)...R]やS[L...(R+1)]はS[L..R]を含むので、f(L-1,R,k)やf(L,R+1,k)は最低f(L,R,k)より大きい。
• S[L-1]==S[R+1]なら、S[(L-1)..(R+1)]とその反転はS[L...R]よりも価値が2大きい
• S[L-1]!=S[R+1]でも、文字変更を1回行うことで上記の状態に持ち込める。

int N,K;
string S;

int dp[303][303][303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>K;
	N=S.size();
	
	FOR(i,N) {
		dp[i][i][K]=1;
		if(i<N-1) {
			dp[i][i+1][K]=1+(S[i]==S[i+1]);
			if(K) dp[i][i+1][K-1]=2;
		}
	}
	
	
	
	for(i=1;i<=N;i++) {
		for(int L=0;L+i<=N;L++) {
			int R=L+i-1;
			for(k=0;k<=K;k++) {
				if(L) dp[L-1][R][k]=max(dp[L-1][R][k],dp[L][R][k]);
				if(R<N-1) dp[L][R+1][k]=max(dp[L][R+1][k],dp[L][R][k]);
				if(L&&R<N-1) {
					if(dp[L][R][k]==0) {
						dp[L-1][R+1][k]=max(dp[L-1][R+1][k],1+(S[L-1]==S[R+1]));
					}
					else {
						dp[L-1][R+1][k]=max(dp[L-1][R+1][k],dp[L][R][k]+2*(S[L-1]==S[R+1]));
					}
					if(k) dp[L-1][R+1][k-1]=max(dp[L-1][R+1][k-1],dp[L][R][k]+2);
				}
			}
		}
	}
	
	int ma=0;
	FOR(i,K+1) ma=max(ma,dp[0][N-1][i]);
	cout<<ma<<endl;
	
}

まとめ

これは手間取ったけど一応解けて良かった。