作者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