裸最长公共子序列
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 using namespace std; 10 11 12 int dp[10005][10005]; 13 int map1[100005],map2[100005]; 14 15 int main() 16 { 17 int num1,num2; 18 int cas=1; 19 while(~scanf("%d %d",&num1,&num2)) 20 { 21 if(num1==0 && num2==0) 22 break; 23 memset(dp,0,sizeof(dp)); 24 for(int i=0;i<num1;i++) 25 scanf("%d",&map1[i]); 26 for(int j=0;j<num2;j++) 27 scanf("%d",&map2[j]); 28 29 for(int i=0;i<num1;i++) 30 for(int j=0;j<num2;j++) 31 { 32 if(map1[i]==map2[j]) 33 dp[i+1][j+1]=dp[i][j]+1; 34 else 35 dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); 36 } 37 printf("Twin Towers #%d Number of Tiles : %d ",cas++,dp[num1][num2]); 38 } 39 return 0; 40 }