Many problems in Computer Science involve maximizing some measure according to constraints.
Consider a history exam in which students are asked to put several historical events into chronological order. Students who order all the events correctly will receive full credit, but how should partial credit be awarded to students who incorrectly rank one or more of the historical events?
Some possibilities for partial credit include:
For example, if four events are correctly ordered 1 2 3 4 then the order 1 3 2 4 would receive a score of 2 using the first method (events 1 and 4 are correctly ranked) and a score of 3 using the second method (event sequences 1 2 4 and 1 3 4 are both in the correct order relative to each other).
In this problem you are asked to write a program to score such questions using the second method.
Given the correct chronological order of n events 
as 
where 
denotes the ranking of event i in the correct chronological order and a sequence of student responses 
where 
denotes the chronological rank given by the student to event i; determine the length of the longest (not necessarily contiguous) sequence of events in the student responses that are in the correct chronological order relative to each other.
The first line of the input will consist of one integer n indicating the number of events with 
. The second line will containn integers, indicating the correct chronological order of n events. The remaining lines will each consist of n integers with each line representing a student's chronological ordering of the n events. All lines will contain n numbers in the range 
, with each number appearing exactly once per line, and with each number separated from other numbers on the same line by one or more spaces.
For each student ranking of events your program should print the score for that ranking. There should be one line of output for each student ranking.
4 4 2 3 1 1 3 2 4 3 2 1 4 2 3 4 1
1 2 3
10 3 1 2 4 9 5 10 6 8 7 1 2 3 4 5 6 7 8 9 10 4 7 2 3 10 6 9 1 5 8 3 1 2 4 9 5 10 6 8 7 2 10 1 3 8 4 9 5 7 6
6 5 10 9
解題思路：
最長公共子序列的應用.之前已經有過一些相對應的練習,不過這道題關於歷史時間的時間排序.其中輸入的序列並不一定代表著時間的順序，而是代表著事件i發生的位置在哪裡.
注意，給出的序列和一般理解上的出現次序是不同的。比如4 2 3 1，一般理解是第4個事件在第1位，第2個事件在第2位，第1個事件在第4位。但在這道題目，序列的含義是第1個事件在第4位，第2個事件在第2位，第4個事件在第一位。為方便計算，需要對輸入的序列進行轉換，使數字對號入座。比如一個正確的序列是：
正確答案 學生答案 含義 輸入的序列 3 1 2 4 9 5 10 6 8 7 2 10 1 3 8 4 9 5 7 6 歷史事件發生在第幾位 轉換後的序列 2 3 1 4 6 8 10 9 5 7 3 1 4 6 8 10 9 5 7 2 發生了第幾個歷史事件
接下來就用轉換後的序列進行計算。為了方便的看出學生答案的順序是否正確，應該按照正確答案與1 2 ... 10的對應關系將學生答案再做一次轉換。正確答案中第2個歷史件事發生在第1位，那麼學生答案中的2應轉換為1；即3轉換為2，以此類推。學生答案就轉換為最終的序列為：
編號 1 2 3 4 5 6 7 8 9 10 序列 2 3 4 5 6 7 8 9 10 1
顯而易見，這個序列的最長有序子串（非連序）的長度為9。要將輸入的正確答案序列和學生答案序列都依次做上述轉換就顯得非常麻煩了，其實正確答案序列是無需轉換的。假設正確答案序列為A，學生答案序列為B，則發生在第Bi位的歷史事件的最終位置就應該是Ai。這樣就可以一次完成全部轉換。
接下來就是要找出最長有序子串。因為正確的順序是由小至大，所以從最後一位開始遍例。依次找出每個數之後（含自身）的最長有序子串長度Mi，然後找最Mi中的最大值即為解。觀查下面的序列：
編號 1 2 3 4 5 6 7 8 9 10 序列 5 8 3 7 6 1 9 2 10 4
因此在進行傳入的參數應該是變換之後的數組。
對於如何將編號轉化為序列號.很簡單的操作：
for(int i=1; i<=n; i++)
{
cin>>loc;//事件i發生的位置loc
x[loc]=i;//
}
完整代碼：
1 #include <bits/stdc++.h>
2 const int MAX=21;
3 int x[MAX];
4 int y[MAX];
5 int DP[MAX][MAX];
6 int b[MAX][MAX];
7 int n,i,j,loc;
8
9 using namespace std;
10
11 void work(int x[],int y[],int n)
12 {
13 memset(DP,0,sizeof(DP));
14 for(i=1; i<=n; i++)
15 {
16 for(j=1; j<=n; j++)
17 {
18 if(x[i]==y[j])
19 {
20 DP[i][j]=DP[i-1][j-1]+1;
21 }
22 else
23 DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
24 }
25 }
26 cout<<DP[n][n]<<endl;
27 }
28
29 int main()
30 {
31 scanf("%d",&n);
32 for(int i=1; i<=n; i++)
33 {
34 cin>>loc;
35 x[loc]=i;
36 }
37 while(~scanf("%d",&loc))//avoid TLE
38 {
39 y[loc]=1;
40 for(int j=2; j<=n; j++)
41 {
42 cin>>loc;
43 y[loc]=j;
44 }
45 work(x,y,n);
46 memset(y,0,sizeof(y));
47 }
48 return 0;
49 }
