ACM POJ 2192 Zipper

题目大意:输入字符串a,b,c 要求推断c是否有a,b中的个字符保持原有顺序组合而成。

算法思想:

DP

用dp[i][j]表示a的前0~i-1共i个字符和b的前0~j-1共j个字符是否构成c[i+j-1].

状态转换方程:

if(i>=1&&c[i+j-1]==a[i-1])

dp[i][j]=dp[i][j]||dp[i-1][j]

if(j>=1&&c[i+j-1]==b[j-1])

dp[i][j]=dp[i][j]||dp[i][j-1]

代码例如以下:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
char a[250];
char b[250];
char c[550];
scanf("%s%s%s",a,b,c);
int la=strlen(a);
int lb=strlen(b);
int lc=strlen(c);
int dp[250][250];
memset(dp,0,sizeof(dp));
dp[0][0]=1;
if(a[0]==c[0])dp[1][0]=1;
if(b[0]==c[0])dp[0][1]=1;
for(int j=0;j<=la;j++){
for(int k=0;k<=lb;k++){
if(k>=1&&c[k+j-1]==b[k-1])
dp[j][k]=dp[j][k]||dp[j][k-1];
if(j>=1&&c[k+j-1]==a[j-1])
dp[j][k]=dp[j][k]||dp[j-1][k];
}
}
if(dp[la][lb])cout<<"Data set "<<i<<": yes"<<endl;
else
cout<<"Data set "<<i<<": no"<<endl;
}
return 0;
}
上一篇:英语初级学习系列-00-Name-介绍自己


下一篇:bookStore案例第一篇【部署开发环境、解决分类模块】