斜率dp

第一道斜率dp题，终于是理解了斜率dp。点亮技能树，我会变的越来越强的！！

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int max_n = 5e5+100;
typedef long long ll;
int n,M;
ll a[max_n];
ll sum[max_n];
deque<int> que;
ll dp[max_n];
bool check(ll k){
    int a = que[0],b=que[1];
    ll x1 = sum[a],y1 = dp[a]+sum[a]*sum[a];
    ll x2 = sum[b],y2 = dp[b]+sum[b]*sum[b];
    if (x1<x2)swap(x1,x2),swap(y1,y2);
    return (y1-y2)<=k*(x1-x2);
}
bool check2(int i){
    int a = que.back(),b=que[que.size()-2];
    ll x1 = sum[a],y1 = dp[a]+sum[a]*sum[a];
    ll x2 = sum[b],y2 = dp[b]+sum[b]*sum[b];
    ll x3 = sum[i],y3 = dp[i]+sum[i]*sum[i];
    if ((x1-x2)*(x3-x2)<0)swap(x1,x2),swap(y1,y2);
    return (y3-y2)*(x1-x2)<=(y1-y2)*(x3-x2);
}
int main(){
    while(~scanf("%d %d",&n,&M)){
        que.clear();
        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];
        que.push_back(0);
        for (int i=1;i<=n;++i){
            ll k = 2*sum[i];
            while (que.size()>=2&&check(k))que.pop_front();
            int j = que.front();
            dp[i]=dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+(ll)M;
            while (que.size()>=2&&check2(i))que.pop_back();
            que.push_back(i);
        }printf("%lld\n",dp[n]);
    }
}