hdu3507 Print Article（斜率优化）

题目
题解
此题是很基础的斜率DP的入门题。
题意很清楚，就是输出序列a[n]，每连续输出的费用是连续输出的数字和的平方加上常数M
让我们求这个费用的最小值。
设dp[i]表示输出前i个的最小费用，那么有如下的DP方程：
$dp\left[i\right]=min\left\{dp\left[j\right]+\left(sum\right[i]-sum[j]{)}^2+M\}\right(0\&lt;j\&lt;i)$dp[i]=min{dp[j]+(sum[i]−sum[j])2+M}(0<j<i)
其中 sum[i]表示数字的前i项和。
相信都能理解上面的方程。
直接求解上面的方程的话复杂度是 $O\left(n^2\right)$O(n2)
对于500000的规模显然是超时的。下面讲解下如何用斜率优化DP使得复杂度降低一维。
我们首先假设在算 dp[i]时， $k\&lt;j$k<j,j点比k点优。
也就是
$dp\left[j\right]+\left(sum\right[i]-sum[j]{)}^2+M\&lt;=dp[k]+(sum\left[i\right]-sum\left[k\right]{)}^2+M;$dp[j]+(sum[i]−sum[j])2+M<=dp[k]+(sum[i]−sum[k])2+M;
所谓j比k优就是DP方程里面的值更小
对上述方程进行整理很容易得到：
$\frac{\left(dp\right[j]+su{m}^2[j\left]\right)-\left(dp\right[k]+su{m}^2[k\left]\right)}{2}\left(sum\right[j]-sum[k\left]\right)\le sum\left[i\right].$2(dp[j]+sum2[j])−(dp[k]+sum2[k])​(sum[j]−sum[k])≤sum[i].
注意整理中要考虑下正负，涉及到不等号的方向。
左边我们发现如果令： $yj=dp\left[j\right]+su{m}^2\left[j\right]$yj=dp[j]+sum2[j]
$xj=2sum\left[j\right]$xj=2sum[j]
那么就变成了斜率表达式： $\frac{yj-yk}{xj-xk}\le sum\left[i\right];$xj−xkyj−yk​≤sum[i];
而且不等式右边是递增的。
所以我们可以看出以下两点：我们令 $g[k,j]=\frac{yj-yk}{xj-xk}$g[k,j]=xj−xkyj−yk​
第一：如果上面的不等式成立，那就说j比k优，而且随着i的增大上述不等式一定是成立的，也就是对i以后算DP值时，j都比k优。那么k就是可以淘汰的。
第二：如果 $k\&lt;j\&lt;i$k<j<i而且 $g[k,j]\&gt;g[j,i]$g[k,j]>g[j,i]那么 j 是可以淘汰的。
假设 $g[j,i]\le sum\left[i\right]$g[j,i]≤sum[i]就是i比j优，那么j没有存在的价值
相反如果 $g[j,i]\&gt;sum\left[i\right]$g[j,i]>sum[i]那么同样有 $g[k,j]\&gt;sum\left[i\right]$g[k,j]>sum[i]那么 k比 j优 那么 j 是可以淘汰的
所以这样相当于在维护一个下凸的图形，斜率在逐渐增大。
通过一个队列来维护。

#include<bits/stdc++.h>
using namespace std;
const int N=500002;
int n,m,dp[N],sum[N],q[N],h,t,i;
#define get(i,j) dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m
#define up(i,j) (dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j])
#define down(i,j) (sum[i]-sum[j])*2
int main(){
    while (~scanf("%d%d",&n,&m)){
        for (i=1;i<=n;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
        h=0;t=1;q[0]=0;
        for (i=1;i<=n;i++){
            while (h+1<t && up(q[h+1],q[h])<=sum[i]*down(q[h+1],q[h])) h++;
            dp[i]=get(i,q[h]);
            while (h+1<t && up(i,q[t-1])*down(q[t-1],q[t-2])<=up(q[t-1],q[t-2])*down(i,q[t-1])) t--;
            q[t++]=i;
        }
        printf("%d\n",dp[n]);
    }
}