Luogu P3648 [APIO2014]序列分割 题解

#include<bits/stdc++.h>
#define LD double
using namespace std;
int n,k,a[100010],q[100010],pre[100010][210];
long long g[100010],f[100010],s[100010];
inline LD slope(int j,int k){
    return s[j]==s[k]?-2000000000.0:(LD)((LD)((g[j]-s[j]*s[j])-(g[k]-s[k]*s[k])))/((LD)(s[k]-s[j]));
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
    for(int t=1;t<=k;t++){
        int l,r;l=r=1;q[1]=0;
        for(int i=1;i<=n;i++){
            while(l<r&&slope(q[l],q[l+1])<=s[i]) ++l;
            f[i]=g[q[l]]+s[q[l]]*(s[i]-s[q[l]]);
            pre[i][t]=q[l];
            while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
            q[++r]=i;
        }
        for(int i=1;i<=n;i++) g[i]=f[i];
    }
    printf("%lld\n",f[n]);
    for(int i=k,t=n;i>=1;i--) t=pre[t][i],printf("%d ",t);printf("\n");
}