Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

转个解题报告。。

Posted by damacheng009 at 2010-11-21 21:33:31 on Problem 1934
这题很难,我只写出了一个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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator