Print Article-斜率优化dp

HDU - 3507 Print Article

$$
\begin{align}
dp_i &= \min_{j=1}^{{i-1}(dp_j+(sum_i-sum_j)}2+m) \
dp_i &= dp_j +sum_i^2+sum_j2-2sum_isum_j+m \
dp_j+sum_j^2 &= 2sum_isum_j+dp_i-sum_i^2-m\
y&=kx+b
\end{align}
$$
其中
$$
y=dp_j+sum_j^2 \
k=2sum_i \
x=sum_j \
b=dp_i-sum_i^2-m
$$

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5e5+10;
bool Mst;int n,m;
int q[maxn];
int dp[maxn],sum[maxn];double slope(int i,int j)
{// x-sum[j], y-dp[j]+sum[j]*sum[j]// so k:(x_1,y_1),(x_2,y_2)=return (double)(dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j])/(sum[i]==sum[j] ? 1e-9 : sum[i]-sum[j]);// (y_1-y_2)/(x_1-x_2)---0-无穷大!!!
}bool Med;
signed main()
{// cerr<<1.0*(&Med-&Mst)/1024/1024<<" M\n";while(~scanf("%lld%lld",&n,&m)){for(int i=1;i<=n;++i){scanf("%lld",sum+i);sum[i]+=sum[i-1];}int h=1,t=0;for(int i=1;i<=n;++i){// h<t 保证队列里至少两个点// 计算到i时，i-1是i的侯选，尝试加入while(h<t && slope(i-1,q[t]) <= slope(q[t],q[t-1])){--t;}q[++t]=i-1;while(h<t && slope(q[h+1],q[h])<=2*sum[i]){++h;}int j=q[h];dp[i]=dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;}printf("%lld\n",dp[n]);}return 0;
}