http://acm.hdu.edu.cn/showproblem.php?pid=4545
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 2000 5 using namespace std; 6 7 char s1[maxn],s2[maxn]; 8 int t,m; 9 int dp[maxn][maxn]; 10 int g[maxn][maxn]; 11 12 int main() 13 { 14 scanf("%d",&t); 15 for(int cas=1; cas<=t; cas++) 16 { 17 scanf("%s",s1+1); 18 scanf("%s",s2+1); 19 scanf("%d",&m); 20 getchar(); 21 memset(g,0,sizeof(g)); 22 for(int i=1; i<=m; i++) 23 { 24 char ch1,ch2; 25 scanf("%c %c",&ch1,&ch2); 26 getchar(); 27 g[ch2-'a'][ch1-'a']=1; 28 } 29 memset(dp,0,sizeof(dp)); 30 int k1=strlen(s1+1); 31 int k2=strlen(s2+1); 32 bool flag=true; 33 for(int i=1; i<=k1; i++) 34 { 35 for(int j=1; j<=k2; j++) 36 { 37 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 38 if(s1[i]==s2[j]||(g[s1[i]-'a'][s2[j]-'a']==1)) 39 { 40 dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1); 41 } 42 } 43 } 44 printf("Case #%d: ",cas); 45 if(dp[k1][k2]==k1) printf("happy "); 46 else printf("unhappy "); 47 } 48 return 0; 49 }