UVa 111 - History Grading

UVa 111 - History Grading題目不難，可以用LCS(Longest Common Subsequence)來解。唯一要注意的是題目所給的輸入資料。

程式碼

例如：
10
3 1 2 4 9 5 10 6 8 7
2 10 1 3 8 4 9 5 7 6

第一數字表示有十個事件。
接下來的每一行裡的數字則是指每一個事件在第幾個順序發生的：
event 1 -> order 3
event 2 -> order 1
event 3 -> order 2
以此類推，所以要先經過轉換後，事件的正確發生順序為2 3 1 4 6 8 10 9 5 7。
下一行經過轉換後，順序為3 1 4 6 8 10 9 5 7 2。
由LCS計算可得到最大的共同子序列長度為9。