題目大意：最長公共子序列。
DP。
注意：每組數(shù)據(jù)之后輸出一個空行。
以下是我的代碼：
#include<algorithm>
#include<cstdio>
using namespace std;
const int kMaxn(107);
int d[kMaxn][kMaxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T(0),n,m;
while(scanf("%d%d",&n,&m)==2 && (n || m))
{
int a[kMaxn],b[kMaxn];
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
d[0][0]=d[0][1]=d[1][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i]==b[j])
d[i][j]=d[i-1][j-1]+1;
else
d[i][j]=max(d[i-1][j],d[i][j-1]);
T++;
printf("Twin Towers #%d\n",T);
printf("Number of Tiles : %d\n\n",d[n][m]);
}
return 0;
}
posted on 2011-05-24 16:14
lee1r 閱讀(363)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃