時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
歷史測驗要求學生替 n 個事件標出年代先後。為了給部分分數，老師採用以下方式：找出一組盡可能多的事件，使它們在學生答案中的相對先後與正確答案一致。這些事件不必在順序中連續，得分為選出的事件數。
輸入的第 i 個數字是「事件 i 的名次」，不是排在第 i 位的事件編號。正確答案 c_i 與學生答案 r_i 都表示事件 i 被排在第幾位。請計算每名學生的得分。
輸入格式
輸入包含一組或多組資料。每組先有一行整數 n，2 ≤ n ≤ 20；下一行有 n 個整數，為正確名次。接下來每行有 n 個整數，為一名學生的名次。
每個名次列都是 1 到 n 的排列，數字間可能有一個或多個空白。新的單一整數行表示下一組資料的 n；讀到檔案結尾為止。
輸出格式
每名學生輸出一行，表示符合正確相對順序的最長事件序列長度。
題目來源：UVa 111 — History Grading。 原題：https://onlinejudge.org/external/1/111.pdf
範例測資
範例輸入 1
4 4 2 3 1 1 3 2 4 3 2 1 4 2 3 4 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
範例輸出 1
1 2 3 6 5 10 9
請先登入後再提交程式碼
討論與題解
載入討論區…