a676. 00111 - History Grading
Tags : DP LIS 最長遞增子序列
Accepted rate : 296人/317人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-05-18 14:49

Content

在資訊科學中有一些是關於在某些條件限制下,找出一些計算的最大值。

以歷史考試來說好了,學生被要求對一些歷史事件根據其發生的年代順序來排列。所有事件順序都正確的學生無疑的可以得滿分。但是那些沒有全對的人又該如何給分呢?以下有2種可能的給分方式:

  1. 每個與標準答案的順序相同的事件得1分
  2. 每個在最長(但不一定要連續)的序列事件中,其相對的順序亦可以在標準答案發現者,每個事件得1分。

舉例說明:如果有4個事件其發生時間的順序依次是1 2 3 4(就是標準答案啦,意思是第1個事件發生順序為1,第2個事件發生的順序為2,......)。所以如果學生回答此4個事件發生的順序依次是1 3 2 4的話,根據上面第1種方法可以得2分(第1個及第4個事件)。但是如果以上面第2種方法可以得3分(1 2 4或者1 3 4其相對的順序可以在標準答案發現)

在本問題中,請你寫一個程式以第2個方法算出學生該得多少分。

 

Input

只考一次試,所以輸入的第1列有一個整數n(2 <= n <= 20)代表此次歷史考試有多少個事件要排序。第2列為標準答案,有n個正整數c1,c2,......cn,(其內容為1到n的某種排列),c1代表第1個事件發生的順序,c2代表第2個事件發生的順序,依此類推。

從第3列開始每列為一學生的答案,每列有n個正整數r1,r2,......rn,(其內容亦為1到n的某種排列),r1代表學生回答第1個事件發生的順序,r2代表學生回答第2個事件發生的順序,依此類推。

 

Output

對每一學生的答案,輸出其所得的分數。

Sample Input #1
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
Sample Output #1
6
5
10
9
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :
Lucky貓 ★★★ 中 英
Tags:
DP LIS 最長遞增子序列
出處:
UVa111 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
30589 hugochu712@g ... (HugoChu) a676
649 2022-05-30 16:41
27086 406490150@gm ... (我是朱朱) a676
997 2021-09-12 15:27
26968 alison.acorn ... (aa w) a676
677 2021-09-05 09:45
24961 allllllan123 ... (God of Computer...) a676
這題應該是 LCS
888 2021-04-07 20:51