poj 2192 记忆化&dfs - c++编程基础

给三个串，问第三个串能否由前两个串构成。。
dfs+剪枝。。
[cpp]
#include
#include
#include
#include
using namespace std;

const int maxn=210;
char sa[maxn],sb[maxn],p[maxn<<1];
//int dp[maxn][maxn];
int lena,lenb,lenp;

bool dfs(int la,int lb,int lp){
if(la==lena&&lb==lenb)return true;
if(la if(dfs(la+1,lb,lp+1))return true;
}
if(lb if(dfs(la,lb+1,lp+1))return true;
}
return false;
}

int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%s%s%s",sa,sb,p);
lena=strlen(sa);
lenb=strlen(sb);
lenp=strlen(p);
printf("Data set %d: ",cas);
if(lena+lenb!=lenp || sa[lena-1]!=p[lenp-1]&&sb[lenb-1]!=p[lenp-1]){puts("no");continue;}
bool OK=dfs(0,0,0);
if(OK)puts("yes");
else puts("no");
}
}

dp 记忆化。。
[cpp]
#include
#include
#include
#include
using namespace std;

const int maxn=210;
char sa[maxn],sb[maxn],p[maxn<<1];
int dp[maxn][maxn];
int lena,lenb,lenp;

bool funDP(int i,int j){
if(dp[i][j]!=-1)return dp[i][j];
if(i==0&&j==0)return dp[i][j]=true;
if(i>0&&sa[i]==p[i+j])if(funDP(i-1,j))return dp[i][j]=true;
if(j>0&&sb[j]==p[i+j])if(funDP(i,j-1))return dp[i][j]=true;
return dp[i][j]=false;
}

int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%s%s%s",sa+1,sb+1,p+1);
lena=strlen(sa+1);
lenb=strlen(sb+1);
lenp=strlen(p+1);
//printf("%d %d %d\n",lena,lenb,lenp);
printf("Data set %d: ",cas);
if(lena+lenb!=lenp || sa[lena]!=p[lenp]&&sb[lenb]!=p[lenp]){puts("no");continue;}
memset(dp,-1,sizeof(dp));
bool OK=funDP(lena,lenb);
if(OK)puts("yes");
else puts("no");
}
}

作者：qingniaofy