频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 2192 记忆化&dfs
2012-08-13 15:46:10           
收藏   我要投稿

给三个串,问 第三个串能否 由前两个串构成。。
dfs+剪枝。。
[cpp] 
#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  记忆化 。。
[cpp] 
#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"); 
    } 

 作者:qingniaofy

点击复制链接 与好友分享!回本站首页
相关TAG标签 记忆
上一篇:hdu 2612
下一篇:文件处理常用方法及link和unlink讲解
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站