题解：斜率优化，维护上凸包，类似右上半圆
滚动数组优化空间，DP时记录决策点
注意：注意sum[i]-sum[j]可能==0
出题人就给了32分QWQ
其实本代码有Bug但是数据没卡
对付直接把0元素去失然后DP可能使得序列不敷m
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=100009; const int maxm=209; typedef long long Lint; int n,m; Lint s[maxn]; int ref[maxn]; Lint f[maxn]; Lint g[maxn]; int p[maxn][maxm]; int q[maxn]; Lint Getk(int i){ return g[i]-s[i]*s[i]; } void putans(int x,int y){ if(y==0)return; putans(p[x][y],y-1); printf("%d ",ref[x]); } int main(){ scanf("%d%d",&n,&m);++m; int cnt=0; for(int i=1;i<=n;++i){ Lint x; scanf("%lld",&x); if(x==0)continue; ++cnt; s[cnt]=s[cnt-1]+x; ref[cnt]=i; } n=cnt; int h,t; for(int j=2;j<=m;++j){ q[h=t=1]=j-1; for(int i=j;i<=n;++i){ while((h<t)&&((Getk(q[h+1])-Getk(q[h]))>-s[i]*(s[q[h+1]]-s[q[h]])))++h; // printf("%d %d %d\n",j,i,q[h]); f[i]=g[q[h]]+(s[i]-s[q[h]])*s[q[h]]; p[i][j]=q[h]; while(h<t){ int a=q[t-1],b=q[t]; if(1.0*(Getk(b)-Getk(a))/(s[b]-s[a])<1.0*(Getk(i)-Getk(b))/(s[i]-s[b]))--t; else break; } q[++t]=i; } for(int i=1;i<=n;++i){ g[i]=f[i];f[i]=0; } } printf("%lld\n",g[n]); // putans(p[n][m],m-1); // printf("\n"); return 0; }
，