uva 111 - History Grading (dp, LCS)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 #define Max(a,b)((a)>(b)?(a):(b))
 8 const int maxn= 20 + 10;
 9 int a[maxn], b[maxn], n, d[maxn][maxn];
10 
11 void LCS()
12 {
13     memset(d, 0, sizeof(d));
14     int i, j;
15     for(i = 1; i <= n; i++)
16     for(j = 1; j <= n; j++)
17     if(a[i]==b[j])
18         d[i][j] = d[i-1][j-1] + 1;
19     else
20         d[i][j] = Max(d[i-1][j], d[i][j-1]);
21     cout<<d[n][n]<<endl;
22 }
23 int main()
24 {
25     int i, x;
26     cin>>n;
27     for(i = 1; i <= n; i++)
28     {
29         cin>>x;
30         a[x] = i;
31     }
32     while(cin>>x)
33     {
34         b[x] = 1;
35         for(i = 2; i <= n; i++)
36         {
37             cin>>x;
38             b[x] = i;
39         }
40         LCS();
41     }
42     return 0;
43 }