Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
转个解题报告。。这题很难,我只写出了一个TLE的版本。 后来找了解题报告,只找到了一个,就是这位alpc43大牛的版本: http://hi.baidu.com/alpc43/blog/item/95184e03a5fef4e209fa932d.html 这个代码很牛逼! 它的思路是: 1)首先按照常规的方法求出最长公共子序列的长度 也就是用O(MN)的那个动态规划,结果放在二维数组dp里 dp[i][j] = { 字串a的1~i部分与字串b的1~j部分的最长公共子序列的长度 } 2)求辅助数组 last1[i][j] = { 到下标i为止,字符j在字串a中最后一次出现的下标 } last2[i][j] = { 到下标i为止,字符j在字串b中最后一次出现的下标 } 3)枚举最长公共字串的每一个字符 从最后一个字符开始枚举 比如说现在枚举最后一个字符是'C'的情况。 那么 'CDCD' 与 'FUCKC' 这两个字串。 一共有 (0, 2) (0, 4) (2, 2) (2. 4) 这四种可能。 很明显前三个是可以舍弃的,因为第四个优于前三个,为后续的枚举提供了更大的空间。 last数组正好是用来做这个的。 4)排序输出 代码里用了stl的set。 注意,由于刚刚的枚举过程是针对每个字符,所以是不用判重的。 这个思路非常之牛逼! Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator