斜率优化——hdu3507

https://blog.bill.moe/1d1d-DP-optimization-notes/#%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 500005
struct point{
    ll x,y;//x=sum[i],y=dp[i]+sum[i]*sum[i]
    point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
    point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
};
ll cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}

ll n,m,dp[N],a[N],sum[N];
point q[N];
int head,tail;
void pop(ll k){//sum[i]显然递增，所以可以把前面斜率<=k的全部pop掉 
    while(tail>head && q[head+1].y-q[head].y<=k*(q[head+1].x-q[head].x))
        head++;
}
void push(point k1){//sum[i]递增，所以必定可以更新凸包
    while(tail>head && cross(q[tail]-k1,q[tail-1]-k1)>=0)tail--;
    q[++tail]=k1;
}

int main(){
    while(cin>>n>>m){
    memset(sum,0,sizeof sum);
    
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    
    dp[0]=0;tail=head=1;
    q[tail]=((point){0,0});
    for(int i=1;i<=n;i++){
        pop(2*sum[i]);//在凸包上找到该斜率对应的点
        dp[i]=q[head].y-q[head].x*q[head].x+(sum[i]-q[head].x)*(sum[i]-q[head].x)+m;
        push((point){sum[i],dp[i]+sum[i]*sum[i]});//把第i个点更新到二维坐标轴上，更新凸包 
        //cout<<i<<" "<<dp[i]<<" "<<q[head].x<<" "<<q[head].y<<" "<<head<<" "<<tail<<endl;
    }
    cout<<dp[n]<<'
';
    }
}