TopCoder SRM 305 Div1 Medium InterleavePal

問題

二つの文字列s,tが与えられる。
s,tをinterleaveに含む文字列の中で、連続する部分文字列のうち回文となっている部分の長さが最長の文字列の、回文となっている部分の長さを求めよ。

文字列Aから（必ずしも連続しない部分文字列として）Bを抜き出した後に、残った文字列がCになっているという意味である。

制約条件

sの長さ≦50
tの長さ≦50

方針

若干問題文の日本語が意味不明だけど、
原文も結構意味不明だった。

動的計画法による。
dp[a][b][c][d]を、sの[a,b)の部分、tの[c,d)の部分を組み合わせて作れる文字の回文になっている部分の長さの最大値とすると、

sから二文字を使う場合と、
tから二文字使う場合と、
sの先頭一文字とtの末尾一文字を使う場合と、
sの末尾一文字とtの先頭一文字を使う場合に分けられる。

それぞれのうち最大値を求めればいい。

一個再帰を深くしたのが、全体が回文になっていて、
しかも両端に同じ文字を付け加えられる場合は、回文の長さに+2をする。

ソースコード

string s,t;
int dp[51][51][51][51];
int rec(int a,int b,int c,int d){
	if(a>=b&&c>=d)return 0;
	
	int &res=dp[a][b][c][d];
	if(res>=0)return res;
	
	if(a<b){
		res=max(res,max(rec(a+1,b,c,d),rec(a,b-1,c,d)));
		int tmp=rec(a+1,b-1,c,d);
		if(tmp==b-a+d-c-2+(a+1==b)&&s[a]==s[b-1])tmp+=a+1==b?1:2;
		res=max(res,tmp);
	}
	if(c<d){
		res=max(res,max(rec(a,b,c+1,d),rec(a,b,c,d-1)));
		int tmp=rec(a,b,c+1,d-1);
		if(tmp==b-a+d-c-2+(c+1==d)&&t[c]==t[d-1])tmp+=c+1==d?1:2;
		res=max(res,tmp);
	}
	if(a<b&&c<d){
		int tmp=rec(a+1,b,c,d-1);
		if(tmp==b-a+d-c-2&&s[a]==t[d-1])tmp+=2;
		res=max(res,tmp);
		tmp=rec(a,b-1,c+1,d);
		if(tmp==b-a+d-c-2&&s[b-1]==t[c])tmp+=2;
		res=max(res,tmp);
	}
	return res;
}

class InterleavePal {
	public:
	int longestPal(string s, string t) 
	{
		::s=s; ::t=t;
		memset(dp,-1,sizeof(dp));
		return rec(0,s.size(),0,t.size());
	}
};