高效算法设计举例(2)
例题21 子序列(Subsequence, SEERC 2006, LA 2678)
简单题
1 |
|
例题22 最大子矩阵(City Game, SEERC 2004, LA 3029)
DP46题之一,算是DP系列的入门题
1 |
|
例题23 遥远的银河(Distant Galaxy, Shanghai 2006, LA 3695)
和上一题(City Game)类似,但这题略复杂。明显每个点的坐标相差太大,第一步需要对坐标进行离散化,然后记录每一个点上面和左面点的个数,最后四个循环解决问题。
1 |
|
例题24 废料堆(Garbage Heap, UVa 10755)
和前两题类似,这题只是将题目维度增加到三维,求立方体的最大价值和,做法差不多,详看白书及代码
1 |
|
例题25 侏罗纪(Jurassic Remains, SEERC 2003, POJ 1903, LA 2965)
最好想的办法是穷举,但复杂度是$O({2}^{n})$,有点大。这题就可以用中途相遇法,先求前$n/2$个字符串能得到的值,再求剩余字符串能得到的值,最后二分判断是否可以相遇
1 |
|