果的LCS,只不过输入的时候有trick
#include <stdio.h>
int n;
int str1[50], str2[50];
int LCS()
{
int dp[50][50], i, j;
for ( i = 0 ; i <= n ; i++ )
dp[i][0]= dp[0][i] = 0;
for ( i = 1 ; i <= n ; i++ )
for ( j = 1 ; j <= n ; j++ )
if (str1[i] == str2[j])
dp[i][j]= dp[i-1][j-1]+1;
else
dp[i][j]= dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
return dp[n][n];
}
int main()
{
scanf("%d", &n);
int i, t;
for ( i = 0 ; i < n ; i++ )
{
scanf("%d", &t);
str1[t]= i+1;
}
while ( EOF != scanf("%d", &t) )
{
str2[t]= 1;
for ( i = 1 ; i < n ; i++ )
{
scanf("%d", &t);
str2[t]= i+1;
}
printf("%d\n", LCS());
}
return 0;
}