c++ 斜率优化DP

#include <bits/stdc++.h>
using namespace std;


typedef long long LL;
const int N=1e5+5;
const int P=105;
const LL INF=0x3f3f3f3f3f3f3f3f3f;

LL f[P][N], s[N], a[N], d[N], q[N], g[N];
int n, m, p, k;

int main(){
    memset(f, 0x3f, sizeof f);
    memset(s, 0x00, sizeof s);
    memset(a, 0x00, sizeof a);
    memset(d, 0x00, sizeof d);
    memset(q, 0x00, sizeof q);
    memset(g, 0x00, sizeof g);
    cin>>n>>m>>p;
    for(int i=2; i<=n; ++i){
        cin>>d[i];
        d[i]+=d[i-1];
    }
    for(int i=1; i<=m; ++i){
        int j;
        cin>>j>>k;
        a[i]=k-d[j];
    }
    sort(a+1, a+m+1);
    for(int i=1; i<=m; ++i) s[i]=s[i-1]+a[i];
    f[0][0]=0;
    int hh=0, tt=0;
    for(int i=1; i<=p; ++i){
        for(int j=1; j<=m; ++j) g[j]=f[i-1][j]+s[j];
        q[hh=tt=0]=0;
        for(int j=1; j<=m; ++j){
            while(hh<tt && g[q[hh+1]]-g[q[hh]]<=a[j]*(q[hh+1]-q[hh])) hh++;
            f[i][j]=min(f[i-1][j], g[q[hh]]+a[j]*(j-q[hh])-s[j]);
            if(g[j]>=INF) continue;
            while(hh<tt && (g[j]-g[q[tt]])*(q[tt]-q[tt-1])<=(g[q[tt]]-g[q[tt-1]])*(j-q[tt])) tt--;
            q[++tt]=j;
        }
    }
    cout<<f[p][m]<<endl;
    return 0;
}