UVA 111 History Grading（题意杀，最长公共子序列）_综合

题目链接：
UVA 111 History Grading
题意:
【题意杀！】
先给出 $n$ 个事件的正确发生时间顺序，在给出一些学生排出来的时间发生时间顺序，有两种得分方式；

　在相应的时间点发生事件相同则得１分
　可以得到的分数等于发生事件的相对时间顺序正确的最长长度

求按照第二种方式可以获得的得分？
$n$ 范围： $2\leq n \leq 20$

$denotes\ the\ ranking\ of\ event\ i\ in\ the\ correct\ chronological\ order$
$you\ are\ asked\ to\ write\ a\ program\ to\ score\ such\ questions\ using\ the\ second\ method$

分析：
看样例我也看了好久才明白是怎么来的。。。。
因为要按照事件的相对发生顺序求最长公共子序列，所以先按照时间对时间发生顺序排序，实际上读入时就是记录时间 $i$ 发生的事件编号 $t$ ，剩下的就是求最长公共子序列了。

#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX_N = 50;int n, tmp;
int dp[MAX_N][MAX_N], base[MAX_N], data[MAX_N];void solve()
{memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if(base[i] == data[j]) dp[i][j] = dp[i - 1][j - 1] + 1;else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}
}int main()
{scanf("%d", &n);for(int i = 1; i <= n; ++i) {scanf("%d", &tmp);base[tmp] = i;}while(~scanf("%d", &tmp)) {data[tmp] = 1;for(int i = 2; i <= n; ++i) {scanf("%d", &tmp);data[tmp] = i;}solve();printf("%d\n", dp[n][n]);}
}