这个题题目意思是给你三个字符串str1,str2,str3.将str3从左自右扫描,去匹配str1和str2中的元素,不可重复,若存在一种匹配方法使得str1和str2都被匹配完全了,则输出yes,否则no

相信大家懂了样例对题意就不纠结了。

题目地址:http://poj.org/problem?id=2192

这个题一看就毛躁的用了搜索,结果发现wa掉了。其实仔细想想搜索确实不是个好办法,考虑到一种情况:

str1:aaaaaaaaaaaaaaaaaaaaaab

str2: aaaaaaaaaaaaaaaaaaaaaac

str3: aaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaab

一开始大概就是因为这种数据过不掉吧。。。再仔细想想就想到dp了,想到dp就发现其实是水题

dp[i][j]为str1中前i个字符和str2中前j个字符能否和str3中前i+j个匹配,如果能为1,否则为0;

动态方程:a.dp[i-1][j]==1&&str1[i-1]==str3[i+j-1]//如果str1前i-1个加上str2前j个是和str3前i+j-1个是匹配的,那么考虑str1第i-1个字符和str3中第i+j-1个字符。

     b.dp[i][j-1]==1&&str2[j-1]==str3[i+j-1]

当a和b任意一个条件满足,则dp[i][j]=1.注意dp[i][j]中的i代表是前i个字符,不是到第i个字符,j也一样,说到这里应该很明白了吧,不明白仔细看看代码吧

下面贴代码:

View Code
 1 //====================================================================
 2 //Name       :
 3 //Author     :hxf
 4 //copyright  :http://www.cnblogs.com/Free-rein/
 5 //Description:
 6 //Data       :2012.8.9
 7 //========================================================================
 8 #include
 9 #include
10 #include
11 #include
12 #include<string.h>
13 #include
14 #include
15 #include
16 #define MAX 100005
17 #define inf 1499999999
18 using namespace std;
19 char st1[205];
20 char st2[205];
21 char st3[410];
22 int dp[205][205];
23 int main()
24 {
25     int n;
26     scanf("%d",&n);
27     int k=0;
28     while(n--)
29     {
30         k++;
31         scanf("%s %s %s",st1,st2,st3);
32         getchar();
33         int k1=strlen(st1);
34         int k2=strlen(st2);
35         memset(dp,0,sizeof(dp));
36         dp[0][0]=1;
37         for(int i=0;i<=k1;i++)
38         {
39             for(int j=0;j<=k2;j++)
40             {
41                 if(i>=1&&dp[i-1][j]==1&&st1[i-1]==st3[i+j-1])
42                     dp[i][j]=1;
43                 if(j>=1&&dp[i][j-1]==1&&st2[j-1]==st3[i+j-1])
44                     dp[i][j]=1;
45             }
46         }
47         if(dp[k1][k2]==1)
48             printf("Data set %d: yes\n",k);
49         else
50             printf("Data set %d: no\n",k);
51     }
52     return 0;
53 }