程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2192 記憶化&dfs

poj 2192 記憶化&dfs

編輯：C++入門知識

給三個串，問第三個串能否由前兩個串構成。。
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");
    }
}