(DP6.1.4.1)UVA 111History Grading(最长递增子序列LIS 的LCS 解法)
/* * UVA_111.cpp * * Created on: 2013年10月13日 * Author: Administrator */#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;const int maxn = 25;int f[maxn][maxn];int st[maxn];int ed[maxn];int main(){int n;scanf("%d",&n);int i,j;for(i = 1 ; i <= n ; ++i){int a;cin >> a;st[a] = i;}while(!cin.eof()){for(i = 1 ; i <= n ; ++i){int a;cin >> a;ed[a] = i;}if(cin.eof()){break;}memset(f,0,sizeof(f));for(i = 1 ; i <= n ; ++i){for(j = 1 ; j <= n ; ++j){f[i][j] = max(f[i-1][j],f[i][j-1]);if(st[i] == ed[j]){f[i][j] = max(f[i][j],f[i-1][j-1] + 1);}}}printf("%d\n",f[n][n]);}return 0;}