POJ 2192 Zipper
题意:解题过程:AC代码:
POJ 2192 Zipper
题目传送门
题意:
给出你三个字符串,问你能否把前两个字符串混合成第三个字符串,使得每个字母在原字符串中的前后顺序不改变。
解题过程:
考虑DP,可以用f[i][j]表示第一个字符串枚举到第i位,第二个字符串枚举到第j位时,能否混合成前第三个字符串前i+j位。然后就是简单的转移了。最后f[len1][len2]就是答案了。
AC代码:
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
const int maxn=
205;
int T;
char s1[maxn],s2[maxn],c[maxn*
2];
int len1,len2,len;
bool f[maxn][maxn];
int main()
{
scanf(
"%d",&T);
int t=
1;
while(T--)
{
printf(
"Data set %d: ",t++);
scanf(
"%s%s%s",s1+
1,s2+
1,c+
1);
len1=
strlen(s1+
1);
len2=
strlen(s2+
1);
len=
strlen(c+
1);
memset(f,
0,
sizeof f);
for(
int i=
1;i<=len1;i++)
{
if(s1[i]==c[i])
{
f[i][
0]=
1;
}
else break;
}
for(
int i=
1;i<=len2;i++)
{
if(s2[i]==c[i])
{
f[
0][i]=
1;
}
else break;
}
for(
int i=
1;i<=len1;i++)
{
for(
int j=
1;j<=len2;j++)
{
if(s1[i]==c[i+j]&&f[i-
1][j])
{
f[i][j]=
1;
}
if(s2[j]==c[i+j]&&f[i][j-
1])
{
f[i][j]=
1;
}
}
}
if(f[len1][len2])
printf(
"yes\n");
else printf(
"no\n");
}
return 0;
}
本人蒟蒻OIer一枚,欢迎加QQ:840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433671.html
相关资源:JAVA上百实例源码以及开源项目