频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 1501 & POJ 2192 Zipper(dp记忆化搜索)
2013-07-31 13:01:42           
收藏   我要投稿

题意:给定三个串,问c串是否能由a,b串任意组合在一起组成,但注意a,b串任意组合需要保证a,b原串的顺序 例如ab,cd可组成acbd,但不能组成adcb。

分析:对字符串上的dp还是不敏感啊,虽然挺裸的....dp[i][j] 表示a串前i个,b串前j个字母能组成c串前i+j个字母。所以dp[lena-1][lenb-1] = 1; 就行了。

从后往前找就很好找了,从c串最后一个字符开始递归搜索。

 

#include <cstdio>   
#include <iostream>   
#include <cstring>   
#include <cmath>   
#include <algorithm>   
# define MAX 222   
using namespace std;  
  
char a[MAX],b[MAX],c[MAX*2];  
int dp[MAX][MAX];  
int lena,lenb,lenc;  
  
int dfs(int i,int j,int k) {  
    //cout << i << ' ' << j << ' ' << k << endl;   
    //cout << a[i] << ' ' <<  b[j] << ' ' << c[k]  << endl;   
    if(dp[i][j] != -1 && i >=0 && j >=0) return dp[i][j];  
    if(k == 0 && (a[i] == c[k] || b[j] == c[k])) return 1;  
    if(i != -1 && a[i] == c[k]) {  
        dp[i][j] = max(dp[i][j],dfs(i-1,j,k-1));  
    }  
    if(j != -1 && b[j] == c[k]) {  
        dp[i][j] = max(dp[i][j],dfs(i,j-1,k-1));  
    }  
    if(dp[i][j] == -1)  
        dp[i][j] = 0;  
    return dp[i][j];  
}  
  
int main() {  
    //freopen("D:\\in.txt","r",stdin);   
    //freopen("D:\\out2.txt","w",stdout);   
    int T;  
    int casee = 1;  
    cin >> T;  
    while(T --) {  
        memset(dp,-1,sizeof(dp));  
        scanf("%s%s%s",a,b,c);  
        printf("Data set %d: ",casee++);  
        lena = strlen(a);  
        lenb = strlen(b);  
        lenc = strlen(c);  
        //cout << lena << ' ' << lenb << ' ' << lenc << endl;   
        if(lena + lenb != lenc) {  
            puts("no");  
            continue;  
        }  
        if(dfs(lena-1,lenb-1,lenc-1)) {  
            puts("yes");  
        }  
        else puts("no");  
    }  
    return 0;  
}  

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
# define MAX 222
using namespace std;

char a[MAX],b[MAX],c[MAX*2];
int dp[MAX][MAX];
int lena,lenb,lenc;

int dfs(int i,int j,int k) {
    //cout << i << ' ' << j << ' ' << k << endl;
    //cout << a[i] << ' ' <<  b[j] << ' ' << c[k]  << endl;
    if(dp[i][j] != -1 && i >=0 && j >=0) return dp[i][j];
    if(k == 0 && (a[i] == c[k] || b[j] == c[k])) return 1;
    if(i != -1 && a[i] == c[k]) {
        dp[i][j] = max(dp[i][j],dfs(i-1,j,k-1));
    }
    if(j != -1 && b[j] == c[k]) {
        dp[i][j] = max(dp[i][j],dfs(i,j-1,k-1));
    }
    if(dp[i][j] == -1)
        dp[i][j] = 0;
    return dp[i][j];
}

int main() {
    //freopen("D:\\in.txt","r",stdin);
    //freopen("D:\\out2.txt","w",stdout);
    int T;
    int casee = 1;
    cin >> T;
    while(T --) {
        memset(dp,-1,sizeof(dp));
        scanf("%s%s%s",a,b,c);
        printf("Data set %d: ",casee++);
        lena = strlen(a);
        lenb = strlen(b);
        lenc = strlen(c);
        //cout << lena << ' ' << lenb << ' ' << lenc << endl;
        if(lena + lenb != lenc) {
            puts("no");
            continue;
        }
        if(dfs(lena-1,lenb-1,lenc-1)) {
            puts("yes");
        }
        else puts("no");
    }
    return 0;
}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 记忆
上一篇:hdu 4605-Magic Ball Game(树状数组)
下一篇:POJ 1637 混合图求欧拉回路 最大流实现
相关文章
图文推荐
点击排行

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

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