Codeforces #358 Div2 D. Alyona and Strings

面倒で余り面白くないかな…。
http://codeforces.com/contest/682/problem/D

問題

２つの文字列S,Tが与えられる。
両文字列に、部分文字列P[1]～P[K]がこの順で含まれるようにP[1]～P[K]を選びたい。
Pの総長の最大値を求めよ。

解法

LCSの変形問題。
LCSに加え「現在何個P[i]を選んだか」「直前のP[i]がまだ続いているか否か」の状態を持ってDPなりメモ化再帰するとO(|S||T|K)で済む。

int N,M,K;
string S,T;
int memo[1010][1010][11][2];

int dpdp(int x,int y,int k,int cont) {
	if(k==0 && cont==0) return 0;
	if(x==N || y==M) return (k==0)?0:-101010;
	if(memo[x][y][k][cont]) return memo[x][y][k][cont];
	int& ret=memo[x][y][k][cont];
	ret = -10101010;
	if(S[x]==T[y]) {
		if(k) ret = max(ret,1+dpdp(x+1,y+1,k-1,1));
		if(cont) ret = max(ret,1+dpdp(x+1,y+1,k,1));
	}
	ret = max(ret,dpdp(x+1,y,k,0));
	ret = max(ret,dpdp(x,y+1,k,0));
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ZERO(memo);
	
	cin>>N>>M>>K;
	cin>>S>>T;
	
	cout<<dpdp(0,0,K,0)<<endl;
	
}

まとめ

TLEが割と怖いサイズ。