这是暴力dp 是正确的

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,V=1e2+5;
int n,m,p,a[N],h[N],t[N],dp[V][N],sum[N];
signed main(){
    cin>>n>>m>>p;
    for(int i=2;i<=n;i++){
        cin>>a[i],a[i]+=a[i-1];
    }
    for(int i=1;i<=m;i++){
        cin>>h[i]>>t[i],t[i]=t[i]-a[h[i]];
    }
    sort(t+1,t+m+1);
    for(int i=1;i<=m;i++){
        sum[i]=sum[i-1]+t[i];
    }
    for(int i=1;i<=m;i++){
        dp[1][i]=t[i]*i-sum[i];
    }
    for(int i=2;i<=p;i++){
        for(int j=1;j<=m;j++){
            dp[i][j]=1e18;
            for(int k=0;k<=min(j,m);k++){
                dp[i][j]=min(dp[i][j],dp[i-1][k]+t[j]*(j-k)-sum[j]+sum[k]);
            }
        }
    }
    cout<<dp[p][m];
}

这是优化后的dp WA#2

#include<bits/stdc++.h>//
using namespace std;
#define int long long
const int N=1e5+5,V=1e2+5,M=1e18;
int n,m,p,a[N],h[N],T[N],dp[V][N],sum[N],node,root;
struct line{
    int k,b;
}l[N];
struct segtree{
    int l,r,id;//id是一条线段
    segtree(){
        l=r=id=0;
    }
}t[N];
int calc(int x,int val){//第x个函数 在x'=val 的取值
    return l[x].k*val+l[x].b;
}
int cmp(int x1,int x2,int val){//有两个函数fx1和fx2 fx1(val)是否>fx2(val)
    if(!x1||!x2){
        return x1>x2;
    }
    return calc(x1,val)<calc(x2,val);
}
void update(int &u,int pos,int l,int r){//更新这个子树 
    if(!u){
        u=++node;
    }
    if(cmp(pos,t[u].id,l)&&cmp(pos,t[u].id,r)){
        t[u].id=pos;
        return;
    }
    if((!cmp(pos,t[u].id,l)&&!cmp(pos,t[u].id,r))||l==r){
        return;
    }
    int mid=(l+r)>>1;
    if(cmp(pos,t[u].id,mid)){
        swap(pos,t[u].id);
    }
    if(cmp(pos,t[u].id,l)){
        update(t[u].l,pos,l,mid);
    }
    if(cmp(pos,t[u].id,r)){
        update(t[u].r,pos,mid+1,r);
    }
}
int query(int u,int val,int l,int r){
    if(l==r){
        return t[u].id;
    }
    int mid=(l+r)>>1,ret;
    if(val<=mid){
        ret=query(t[u].l,val,l,mid);
    }
    else{
        ret=query(t[u].r,val,mid+1,r);
    }
    if(cmp(t[u].id,ret,val)){
        ret=t[u].id;
    }
    return ret;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>p;
    for(int i=2;i<=n;i++){
        cin>>a[i],a[i]+=a[i-1];
    }
    for(int i=1;i<=m;i++){
        cin>>h[i]>>T[i],T[i]=T[i]-a[h[i]];
    }
    sort(T+1,T+m+1);
    for(int i=1;i<=m;i++){
        sum[i]=sum[i-1]+T[i];
    }
    for(int i=1;i<=m;i++){
        dp[1][i]=T[i]*i-sum[i];
    }
    for(int i=2;i<=p;i++){
        for(int i=1;i<=node;i++){
            t[i].l=t[i].r=t[i].id=0;
        }
        node=root=0;
        for(int j=1;j<=m;j++){
            l[j].k=j,l[j].b=dp[i-1][j]+sum[j],update(root,j,-M,M),dp[i][j]=min(T[j]*j-sum[j],calc(query(root,-T[j],-M,M),-T[j])+T[j]*j-sum[j]);
        }
    }
    cout<<dp[p][m];
}