作者burgi (burgi)
看板ACMCLUB
標題ACM 111
時間Thu Jan 16 20:55:21 2003
題目說明:
在某次歷史考試中,老師會給學生一堆事件,
假設有10個事件,將其由1~10分別編號,
要求學生將其依事件發生的先後順序來排列,
假設正確答案為3 1 2 4 9 5 10 6 8 7
而學生的回答為4 7 2 3 10 6 9 1 5 8
比較這兩個字串,
求出兩字串Longest common subsequence的長度,
則該長度即為學生的分數
解法:
input是該事件的rank,
即代表該事件是第幾個發生的,
例如:3 1 2 4 9 5 10 6 8 7 (數字代表rank)
代表編號1的事件是第三個發生
2 一
3 二
4 四
.......
那麼將其轉為按順序來排列
=> 2 3 1 4 6 8 10 9 5 7 (數字代表事件編號)
將下來只要求字串的LCS長度
X_1 X_2 X_3......X_i
Y_1 Y_2 .........Y_j
假設兩字串分別為 X_1~X_i Y_1~Y_j
C[i,j]代表其LCS的長度,
C[i,j]的式子如下
C[i,j] = (1) 0 if i=0 or j =0
(2) C[i-1,j-1]+1 if X_i = Y_j
(3) MAX{ C[i-1,j] , C[i,j-1] } if X_i != Y_j
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.244.71