其实就是求两个序列的最长公共子序列
代码如下:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int n1,n2,Case=0; while(scanf("%d%d",&n1,&n2)&&n1) { int a[110],b[110]; int dp[110][110],i,j; memset(dp,0,sizeof(dp)); for(i=1;i<=n1;i++) scanf("%d",&a[i]); for(j=1;j<=n2;j++) scanf("%d",&b[j]); for(i=1;i<=n1;i++) for(j=1;j<=n2;j++) { if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } printf("Twin Towers #%d\n",++Case); printf("Number of Tiles : %d\n\n",dp[n1][n2]); } return 0; }