Codeforces #683 Div1 B. Catching Cheaters

なるほど。
https://codeforces.com/contest/1446/problem/B

問題

2つの文字列C,Dに対し、そのスコアはf(C,D)=4*LCS(C,D)-|C|-|D|で与えられる。

2つの文字列A,Bが与えられる。
Aの連続部分文字列A'とBの連続部分文字列B'のうち、f(A',B')の最大値を求めよ。

解法

dp(x,y) := Aのx文字目以降何文字かからなる部分文字列と、Bのy文字目以降何文字かからなる部分文字列からなるスコアの最大値
とする。

• A[x]=B[y]ならdp(x,y) = 2+dp(x+1,y+1)
• そうでないならdp(x,y) = max(0, dp(x+1,y)-1,dp(x,y+1)-1)

とすればよい。スコアが負とならないようにすること＝スコアが下がるsuffixを切り落とすことに相当する。

int N,M;
string A,B;
int dp[5050][5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>A>>B;
	
	int ma=0;
	FOR(x,N+1) FOR(y,M+1) {
		int v=dp[x][y];
		ma=max(ma,v);
		dp[x+1][y]=max(dp[x+1][y],v-1);
		dp[x][y+1]=max(dp[x][y+1],v-1);
		if(x<N&&y<M&&A[x]==B[y]) dp[x+1][y+1]=max(dp[x+1][y+1],v+2);
	}
	
	cout<<ma<<endl;
}

まとめ

これはDiv1 Bにしては簡単かな。