ZOJ 2633 Full of Painting II 搜索减枝

题目大意是一个线段分成n段涂色，有m种颜色可用，给出每种颜色的费用，每一段规定了所用的颜色以及涂色长度区间。同种颜色的涂色长度不能相同，求是否能按要求完成涂色以及最少需要花费的费用。

很典型的搜索题，主要用到了2个减枝技巧：

1. 预处理出搜索到第i段时，第i+1段到第n段的涂色区间长度范围，如果剩余长度不在此范围内则可减枝。
2. 预处理出搜索带第i段时，要用第i+1段到第n段规定的颜色完成剩余长度的涂色所需的最小费用。如果最小费用与当前费用之和大于或等于当前最优费用则可减枝。

其中第二个预处理通过O(nl^2)的DP完成。

2353428    2010-11-19 02:08:21     Accepted    2633    C++    1320    212    IwfWcf