/**************************************
Problem: UVA 10066 The Twin Towers
Time: 0.000 s
Accepted Time: 2009-04-13 09:10:32
Tips: 最长公共子序列
**************************************/
#include <stdio.h>
int main()
{
int nCase=1,n1,n2;
while(1)
{
scanf("%d%d",&n1,&n2);
if(n1==0&&n2==0)break;
int a[110],b[110],i,j;
for(i=1;i<=n1;i++)scanf("%d",&a[i]);
for(i=1;i<=n2;i++)scanf("%d",&b[i]);
int table[110][110];
for(i=0;i<=n1;i++)table[i][0]=0;
for(i=0;i<=n2;i++)table[0][i]=0;
for(i=1;i<=n1;i++)
for(j=1;j<=n2;j++)
{
if(a[i]==b[j])table[i][j]=table[i-1][j-1]+1;
else if(table[i-1][j]>table[i][j-1])table[i][j]=table[i-1][j];
else table[i][j]=table[i][j-1];
}
printf("Twin Towers #%d\nNumber of Tiles : %d\n\n",nCase++,table[n1][n2]);
}
return 0;
}
Problem: UVA 10066 The Twin Towers
Time: 0.000 s
Accepted Time: 2009-04-13 09:10:32
Tips: 最长公共子序列
**************************************/
#include <stdio.h>
int main()
{
int nCase=1,n1,n2;
while(1)
{
scanf("%d%d",&n1,&n2);
if(n1==0&&n2==0)break;
int a[110],b[110],i,j;
for(i=1;i<=n1;i++)scanf("%d",&a[i]);
for(i=1;i<=n2;i++)scanf("%d",&b[i]);
int table[110][110];
for(i=0;i<=n1;i++)table[i][0]=0;
for(i=0;i<=n2;i++)table[0][i]=0;
for(i=1;i<=n1;i++)
for(j=1;j<=n2;j++)
{
if(a[i]==b[j])table[i][j]=table[i-1][j-1]+1;
else if(table[i-1][j]>table[i][j-1])table[i][j]=table[i-1][j];
else table[i][j]=table[i][j-1];
}
printf("Twin Towers #%d\nNumber of Tiles : %d\n\n",nCase++,table[n1][n2]);
}
return 0;
}