poj 2192 记忆化&dfs

给三个串，问 第三个串能否 由前两个串构成。。

dfs+剪枝。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
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<lena&&sa[la]==p[lp]){
		if(dfs(la+1,lb,lp+1))return true;
	}
	if(lb<lenb&&sb[lb]==p[lp]){
		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  记忆化 。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
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");
	}
}