首页 > 代码库 > 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 剪枝