마법 꾸러미

 1 /*HDU4545        +    */
 2 
 3 
 4 #include
 5 #include<string.h>
 6 #include
 7 using namespace std;
 8 int dp[2][1010];
 9 char a[1010],b[1010];
10 int hash[1010][1010];
11 int LCS(int n,int m)
12 {
13     memset(dp,0,sizeof(dp));
14     int i,j;
15     for(i=1;i<=n;i++)
16         for(j=1;j<=m;j++)
17         {
18             if(a[i-1]==b[j-1] || hash[b[j-1]][a[i-1]])
19             {
20                 dp[i%2][j]=dp[(i-1)%2][j-1]+1;
21             }
22             else if(dp[(i-1)%2][j]>=dp[i%2][j-1])
23             {
24                 dp[i%2][j]=dp[(i-1)%2][j];
25 
26             }
27             else
28             {
29                 dp[i%2][j]=dp[i%2][j-1];
30             }
31         }
32     return dp[n%2][m];
33 }
34 int main()
35 {
36     int n,m;
37     int T,k;
38     int cas=0;
39     char s[2],t[2];
40     scanf("%d",&T);
41     while(T--)
42     {
43         memset(hash,0,sizeof(hash));
44         scanf("%s%s",a,b);
45         n=strlen(a);
46         m=strlen(b);
47         //printf("%s
%s
",a,b);
48         scanf("%d",&k);
49         while(k--)
50         {
51             scanf("%s%s",s,t);
52             hash[s[0]][t[0]]=1;
53             //printf("%s %s
",s,t);
54         }
55         int sum=LCS(n,m);
56         //printf("sum=%d
",sum);
57         if(sum==n) printf("Case #%d: happy
",++cas);
58         else printf("Case #%d: unhappy
",++cas);
59     }
60     return 0;
61 }
62 /*
63 2
64 abba
65 addba 
66 1
67 d b
68 a
69 dd
70 0
71 */