给三个串,问 第三个串能否 由前两个串构成。。
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");
}
}
分享到:
相关推荐
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码