PKU演習問メモ(8/9)

全く練習の成果が出ない。DP解けるようにならねえ。。。

No.	問題名	問題の種類および解法	難易度
2192	Zipper	動的計画法	★★☆☆☆

2192 Zipper

問題概要

文字列A,B,Cが与えられる。
A,Bの文字列をそれぞれの順番は変えず、任意に組み合わせてCの文字列を作れるかを判定せよ。
（例えば、catとtrerからtcraeteなどが作れる）

Cの文字数はAとBの文字数の和であり、A,Bの文字数は200以下である。

解法

動的計画法による。
dp[i][j]を、「Cのi文字までを、Aの先頭からj文字までと、Bの先頭からi-j文字までを使って作れるか」とすると、
dp[i+1][j+1]=dp[i][j] (A[j]==C[i]のとき)
dp[i+1][j]=dp[i][j] (B[i-j]==C[i]のとき）の漸化式が成り立つので解ける。

ソースコード

char A[201],B[201],C[401];
bool dp[2][201];

int main()
{
	int cs; scanf("%d",&cs);
	rep(CS,cs)
	{
		scanf("%s %s %s",A,B,C);
		int l=strlen(A),m=strlen(B),n=strlen(C);
		
		rep(i,l+1)dp[0][i]=0; dp[0][0]=1;
		int cur=0,next=1;
		rep(i,n)
		{
			fill_n(dp[next],l+1,0);
			rep(j,i+1)if(dp[cur][j])
			{
				if(j<l&&A[j]==C[i])dp[next][j+1]=1;
				if(i>=j&&B[i-j]==C[i])dp[next][j]=1;
			}
			swap(cur,next);
		}
		printf("Data set %d: %s\n",CS+1,dp[cur][l]?"yes":"no");
	}
	return 0;
}