开发者社区> 华山青竹> 正文

poj 2192 Zipper

简介: 题目链接:http://poj.org/problem?id=2192 Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 18658   Accepted: 6651 Description Given ...
+关注继续查看

题目链接:http://poj.org/problem?id=2192

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 18658   Accepted: 6651

Description

Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order. 

For example, consider forming "tcraete" from "cat" and "tree": 

String A: cat 
String B: tree 
String C: tcraete 

As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming "catrtee" from "cat" and "tree": 

String A: cat 
String B: tree 
String C: catrtee 

Finally, notice that it is impossible to form "cttaree" from "cat" and "tree". 

Input

The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line. 

For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive. 

Output

For each data set, print: 

Data set n: yes 

if the third string can be formed from the first two, or 

Data set n: no 

if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example. 

Sample Input

3
cat tree tcraete
cat tree catrtee
cat tree cttaree

Sample Output

Data set 1: yes
Data set 2: yes
Data set 3: no

Source

题目大意:

给出两串,从两个串取出字符重新组合,看能否组成第三个串。要求:从第一个串取出的字符在第三个串中的顺序不变,第二个串取出的字符在第三个串中的顺序也不变。

算法分析:

此题深搜和DP都能解决:

深搜的话需要几个强有力剪枝条件

1、  第三个串最后一个字符要么是串1的最后一个字符,要么是串2的最后一个字符

2、  按照串1的顺序对串3进行搜索,若不匹配则该字符必是串2的下一个字符。

参考来源:http://www.cnblogs.com/yu-chao/archive/2012/02/26/2369052.html

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 char first[202],second[202],third[402],Left[401];
 6 int sign[402];
 7 bool flag;
 8 int check()
 9 {
10     int i,count=0;
11     int k=strlen(third);
12     for(i=0;i<k;i++)
13         if(!sign[i]) Left[count++]=third[i];
14     Left[count]='\0';
15     if(strcmp(Left,second)==0) return 1;
16     return 0;
17 }
18 int dfs(int f,int s,int t)
19 {
20     if(f>=strlen(first))
21     {
22         if(check()) flag=true;
23         return 0;
24     }
25     if(flag) return 0;
26     if(first[f]==third[s])
27     {
28         sign[s]=1;
29         if(s<strlen(third)) dfs(f+1,s+1,t);
30         sign[s]=0;
31     }
32     else
33     {
34         if(third[s]!=second[t]) return 0;//剪枝2
35     }
36     if(!flag && s<strlen(third)) dfs(f,s+1,t+1);
37     return 0;
38 }
39 int main()
40 {
41     int len1,len2,len3,Case,count=0;
42     scanf("%d",&Case);
43     while(Case--)
44     {
45         count++;
46         flag=false;
47         scanf("%s %s %s",first,second,third);
48         memset(sign,0,sizeof(sign));
49  
50         len1=strlen(first);
51         len2=strlen(second);
52         len3=strlen(third);
53  
54         if(len1+len2!=len3)
55         {
56             printf("Data set %d: no\n",count);
57             continue;
58         }
59         if(third[len3-1]!=first[len1-1] && third[len3-1]!=second[len2-1])// 剪枝1
60         {
61             printf("Data set %d: no\n",count);
62             continue;
63         }
64         dfs(0,0,0);
65         if(flag) 
66             printf("Data set %d: yes\n",count);
67         else
68             printf("Data set %d: no\n",count);
69     }
70     return 0;
71 }
View Code

动规算法:(参考来源

最优子结构分析:如上例,如果A、B可以组成C,那么,C最后一个字母,必定是 A 或 B 的最后一个字母组成。
C去除除最后一位,就变成是否可以求出 A-1和B 或者 A与B-1 与 是否可以构成 C-1。。。
 状态转移方程:
用f[i][j] 表示 A前 i 位 和B 前j 位是否可以组成 C的前i+j位

             dp[i][j]= (dp[i-1][j]&&(a[i]==c[i+j]))||(dp[i][j-1]&&(b[j]==c[i+j]))

 1 #include<stdio.h>
 2 #include<string.h>
 3  
 4 char a[201],b[201],c[402];
 5 int la,lb,lc;
 6 int dp[201][201];
 7  
 8 int main()
 9 {
10     int ncase;
11     scanf("%d",&ncase);
12     for(int n=1; n<=ncase; n++) {
13          
14         a[0]='p';
15         b[0]='p';
16         c[0]='p';
17          
18         scanf("%s%s%s",a+1,b+1,c+1);
19          
20         la=strlen(a);
21         lb=strlen(b);
22         lc=strlen(c);
23          
24         la-=1;
25         lb-=1;
26          
27         //处理边界
28         for (int i=1; i<=la; i++)
29             if (a[i]==c[i]) dp[i][0]=1;
30          
31         for (int i=1; i<=lb; i++)
32             if (b[i]==c[i]) dp[0][i]=1;
33         //DP
34         for (int i=1; i<=la; i++)
35             for (int j=1; j<=lb; j++)
36                 dp[i][j]= (dp[i-1][j]&&(a[i]==c[i+j]))||(dp[i][j-1]&&(b[j]==c[i+j]));
37          
38         printf("Data set %d: ",n);
39         if (dp[la][lb]==1) printf("yes\n");
40         else printf("no\n");
41          
42     }
43 }

虽然代码简洁明了易理解,但是个人感觉下面的代码更准确一些。

 

来源:http://www.cnblogs.com/yu-chao/archive/2012/02/26/2369052.html

若用DP来作先定义res[i][j]=1表示串1前i个字符和串2的前j个字符能组成串3的前i+j个字符,res[i][j]=0则不能。

状态转移方程如下:

Res[i][j]= (third[i+j]==first[i] && res[i-1][j]==1) ||(third[i+j]==second[j]&&res[i][j-1]==1)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 char first[201],second[201],third[401];
 6 int res[201][201];
 7 int init(int n,int m)
 8 {
 9     int i;
10     for(i=1;i<=m;i++)
11         if(second[i]==third[i]) res[0][i]=1;
12         else break;
13     for(i=1;i<=n;i++)
14         if(first[i]==third[i]) res[i][0]=1;
15         else break;
16     return 0;
17 }
18 int dp(int n,int m)
19 {
20     int i,j;
21     for(i=1;i<=n;i++)
22         for(j=1;j<=m;j++)
23         {
24             if(third[i+j]==first[i] && res[i-1][j]) res[i][j]=1;
25             if(third[i+j]==second[j] && res[i][j-1]) res[i][j]=1;
26         }
27     if(res[n][m]) return 1;
28     return 0;
29 }
30 int main()
31 {
32     int n,len1,len2,count=0;;
33     scanf("%d",&n);
34     while(n--)
35     {
36         count++;
37         scanf("%s %s %s",first+1,second+1,third+1);
38         len1=strlen(first+1);
39         len2=strlen(second+1);
40         memset(res,0,sizeof(res));
41         init(len1,len2);
42     
43         if(dp(len1,len2))
44             printf("Data set %d: yes\n",count);
45         else
46             printf("Data set %d: no\n",count);
47     }
48     return 0;
49 }
View Code

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15761 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19073 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28293 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
13201 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23541 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20272 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14878 0
+关注
华山青竹
一个喜欢玩代码的小青年呵呵呵
543
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载