98
uva 111 - History Grading LCS
一开始想拿它联系下nlogn的lcs，结果发现n^2才0.022s就算了，nlogn是把LCS编程LIS，然后二分查找
注意输入形式
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int A[22],B[22],n;
int LCS()
{
int c[22][22],i,j;
for(i=0;i<=n;i++)c[i][0]=c[0][i]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(A[i]==B[j])c[i][j]=c[i-1][j-1]+1;
else c[i][j]=max(c[i][j-1],c[i-1][j]);
return c[n][n];
}
int main()
{
scanf("%d",&n);
int i,t;
for(i=1;i<=n;i++)
scanf("%d",&t),A[t]=i;
while(~scanf("%d",&t))
{
B[t]=1;
for(i=2;i<=n;i++)
scanf("%d",&t),B[t]=i;
int ans=LCS();
printf("%d\n",ans);
}
}
最后更新：2017-04-03 16:48:43