UVA 10192 Vacation

裸最长公共子序列
 1 #include<time.h>
 2 #include <cstdio>  
 3 #include <iostream>  
 4 #include<algorithm>
 5 #include<math.h> 
 6 #include <string.h>  
 7 #include<vector> 
 8 #include<queue>
 9 #include<set>
10 #include<iterator>
11 using namespace std;
12 
13 
14 int dp[10005][10005];
15 char str1[1005],str2[1005]; 
16 
17 int main()
18 {
19     int len1,len2;
20     int cas=1;
21     while(gets(str1))
22     {
23         
24         if(str1[0]=='#')
25             break;
26         gets(str2);
27         memset(dp,0,sizeof(dp));
28         len1=strlen(str1);
29         len2=strlen(str2);
30         
31         for(int i=0;i<len1;i++)
32             for(int j=0;j<len2;j++)
33             {
34                 if(str1[i]==str2[j])
35                     dp[i+1][j+1]=dp[i][j]+1;
36                 else
37                     dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
38             }
39         printf("Case #%d: you can visit at most %d cities.
",cas++,dp[len1][len2]);
40     }
41     return 0;
42  }