首页 > 代码库 > Uva111最长公共子序列

Uva111最长公共子序列

题意:给你n个时间发生的序号,问你现在又n个时间发生的序号与给定的时间相同的有几个。

思路:知道位置后,求一次最长公共子序列。

#include <stdio.h>#include <string.h>const int maxn = 109;int dp[maxn][maxn];int a[maxn];int b[maxn];inline int max(int a,int b){return a > b ? a : b;}int main(){	int i,n,j;	scanf("%d",&n);	int pos;	for(i=1; i<= n;i++)	{		scanf("%d",&pos);		a[pos] = i;	}	while(~scanf("%d",&pos))	{		b[pos] = 1;		memset(dp,0,sizeof(dp));		for(i = 2;i<= n; i++)		{			scanf("%d",&pos);			b[pos] = i;		}		for(i=1;i<=n;i++)		{			for(j=1;j<=n;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("%d\n",dp[n][n]);	}		return 0;}