首页 > 代码库 > DP 剪枝

DP 剪枝

DP其实也是和搜索一样可以有剪枝的,昨晚看到一个超级好的DP剪枝题:(HDU - 5009)

N段东东,要染色,每次给一个区间染色需要的花费为  该区间颜色总数的平方。  每一段只能被染一次色。求 最少花费将所有区间染色。 N<=500000;

 

这题也是很容易想到方程:F[j] 表示前i段的最小花费,F[j]=min{F[k]+sum[k+1][j]} (k<i) 。  复杂度为O(N^2),但是数据范围大的BT。。所以需要优化。而本题貌似没法用一个辅助数组来草。。所以需要从题目本身的限制条件出发找到优化

优化A:首先对于一个长度为len的区间,我每次只染一小段,也只要len^2的花费,所以转移的时候,当k不断减小时,颜色也越来越多,当颜色的总数为cnt时,最后一次染色的花费是cnt*cnt,显然如果cnt*cnt>=i的话,还不如直接每次只染一小段,所以循环就可以停止了。

优化B:比如数据3 4 2 4 4 2 4 3 2 2。 现在要求F[9],当k减少到6的时候,最后一次染色的区域是[4 3 2 2]。有3种颜色,那就太亏了。因为之前是[3 4 2 4 4 2],这些如果跟着一起涂,那么仍然是3^2的代价,但前面的数字变少了,显然这种更优。。  所以 假设 求F[i]的时候, 前面的颜色为 [ [...]z x y x] ,那么 k枚举到左边那个x 的位置的时候,肯定还不如最后一次把那个x也一起涂掉,也就是肯定不比k枚举到z的时候优。。所以就可以把左边那个x给删掉,具体删除的话就用一个双向链表。也就是如果有多个x,只要保留最右边的那个x就可以。

 

优化的核心代码:

 1         dp[0] = 0, pre[0] = -1; 2         for (int i = 1; i <= n; i++) { 3             if (!mp.count(a[i])) mp[a[i]] = i; 4             else { 5                 int id = mp[a[i]]; 6                 nxt[pre[id]] = nxt[id]; 7                 pre[nxt[id]] = pre[id]; 8                 mp[a[i]] = i; 9             }10  11             int cnt = 0;12             for (int j = pre[i]; j != -1; j = pre[j]) {13                 cnt++;14                 dp[i] = min(dp[i], dp[j] + cnt * cnt);15                 if (cnt * cnt > i)16                     break;17             }18         }

可以参考代码出处http://www.2cto.com/kf/201410/340390.html 

DP 剪枝