<题目链接>
< 转载于>>> >
题目大意：
给你一段数字序列，将它分成任意段数，每一段的费用为这段数字的总和的平方+M，让我们求出这段序列的最小费用。
解题分析：
设dp[i]表示输出前i个的最小费用，那么有如下的DP方程：
dp[i]= min{ dp[j]+(sum[i]-sum[j])^2 +M } 0<j<i
其中 sum[i]表示数字的前i项和。
相信都能理解上面的方程。
直接求解上面的方程的话复杂度是O(n^2)
对于500000的规模显然是超时的。下面讲解下如何用斜率优化DP使得复杂度降低一维。
我们首先假设在算 dp[i]时，k<j ,j点比k点优。
也就是
dp[j]+(sum[i]-sum[j])^2+M <= dp[k]+(sum[i]-sum[k])^2+M;
所谓j比k优就是DP方程里面的值更小
对上述方程进行整理很容易得到：
[(dp[j]+sum[j]*sum[j])-(dp[k]+sum[k]*sum[k])] / 2(sum[j]-sum[k]) <=sum[i].
注意整理中要考虑下正负，涉及到不等号的方向。
左边我们发现如果令： yj=dp[j]+sum[j]*sum[j] xj=2*sum[j]
那么就变成了斜率表达式：（yj-yk）/(xj-xk) <= sum[i];
而且不等式右边是递增的。
所以我们可以看出以下两点：我们令 g[k,j]=(yj-yk)/(xj-xk)
第一：如果上面的不等式成立，那就说j比k优，而且随着i的增大上述不等式一定是成立的，也就是对i以后算DP值时，j都比k优。那么k就是可以淘汰的。
第二：如果 k<j<i 而且 g[k,j]>g[j,i] 那么 j 是可以淘汰的。
假设 g[j,i]<sum[i] 就是i比j优，那么j没有存在的价值
相反如果 g[j,i]>sum[i] 那么同样有 g[k,j]>sum[i] 那么 k比 j优 那么 j 是可以淘汰的
//以上就是斜率优化的证明过程
所以这样相当于在维护一个下凸的图形，斜率在逐渐增大。
通过一个队列来维护。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; const int MAXN = 500010; int dp[MAXN]; int q[MAXN]; //模拟队列 int sum[MAXN]; int head, tail, n, m; // dp[i]= min{ dp[j]+M+(sum[i]-sum[j])^2 }; int getDP(int i, int j) //对该决策点进行dp运算 { return dp[j] + m + (sum[i] - sum[j])*(sum[i] - sum[j]); } int getUP(int j, int k) //yj-yk部分(dy) { return dp[j] + sum[j] * sum[j] - (dp[k] + sum[k] * sum[k]); } int getDOWN(int j, int k) //dx { return 2 * (sum[j] - sum[k]); } int main() { while (scanf("%d%d", &n, &m) == 2) { for (int i = 1; i <= n; i++) scanf("%d", &sum[i]); sum[0] = dp[0] = 0; for (int i = 1; i <= n; i++) //sum[i]数组为前缀和数组 sum[i] += sum[i - 1]; head = tail = 0; q[tail++] = 0; for (int i = 1; i <= n; i++) { //把斜率转成相乘，注意顺序，否则不等号方向会改变的 while (head + 1<tail && getUP(q[head + 1], q[head]) <= sum[i] * getDOWN(q[head + 1], q[head])) head++; //起着更新决策点的作用，并且维护下凸曲线 dp[i] = getDP(i, q[head]); while (head + 1<tail && getUP(i, q[tail - 1])*getDOWN(q[tail - 1], q[tail - 2]) <= getUP(q[tail - 1], q[tail - 2])*getDOWN(i, q[tail - 1])) tail--; //这个语句起着删除上凸点的作用 q[tail++] = i; } printf("%d\n", dp[n]); } return 0; }
2018-07-28
HDU 3507 Print Article（dp+斜率优化）
原文：https://www.cnblogs.com/00isok/p/9383258.html