主題

ZeroJudge - a676: 00111 - History Grading 解題心得

Not In My Back Yard | 2021-04-09 00:00:04 | 巴幣 0 | 人氣 30

題目連結:


題目大意:
輸入第一列給定一正整數 n (2 ≦ n ≦ 20),代表歷史上有 n 個事件。接著的一列給定 n 個正整數,為整數 1 ~ n 的一種排列。其中第一個整數代表第一個事件發生的相對順序、第二個整數代表第二個事件發生的相對順序……以此類推,代表本次歷史測驗的標準答案。

接著有若干列,每列給定 n 個正整數,同樣也是整數 1 ~ n 的一種排列(意義類似於上面)。代表某位學生的所填寫的順序。

評分方式為:該學生寫出來的歷史事件順序(事件 a → 事件 b → 事件 c …… 之序列,不是學生填寫的順序「本身」之序列)與標準答案的序列比較中,同樣出現於標準答案中最長的學生事件順序之子序列的長度即是分數值。

試問,每位學生的分數為何?



範例輸入:
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


解題思維:
稍微變形的最長共同子序列(Longest Common Subsequence,LCS)之題型。因為比較的要是歷史事件,而不是順序本身。所以,例如當給定順序
5 4 1 2 3
代表的是
事件 3 → 4 → 5 → 2 → 1
而我們應該要比較的是下面的 3 4 5 2 1 ,而非原先給定的 5 4 1 2 3。兩者出來的結果會不同,而後者才是題目所求。

至於 LCS 的做法,參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作