# P3648 [APIO2014]序列分割（斜率优化dp）

P3648 [APIO2014]序列分割

\$s[i]\$为元素前缀和，那么

\$f[k][i]=f[k-1][j]+s[j]*(s[i]-s[j])\$

\$f[i]=g[j]+s[j]*(s[i]-s[j])\$

\$g[j]-s[j]^{2}=-s[i]*s[j]+f[i]\$

\$y=g[j]-s[j]^{2}\$

\$k=-s[i]\$

\$x=s[j]\$

\$b=f[i]\$

\$x,k\$单调递增，于是我们直接上单调队列维护下凸包就好辣

```#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
using namespace std;
typedef long long ll;
#define N 100005
ll s[N],f[N],g[N];
int n,k,L,R,h[N],p[205][N];
inline ll X(int x){return s[x];}
inline ll Y(int x){return g[x]-s[x]*s[x];}
inline ll KK(ll xa,ll ya,ll xb,ll yb){return ya*xb-yb*xa;}
int main(){
scanf("%d%d",&n,&k);
for(rint i=1;i<=n;++i)
scanf("%lld",&s[i]),s[i]+=s[i-1];
for(rint j=1;j<=k;++j){
h[L=R=1]=0;
for(rint i=1;i<=n;++i){
while(L<R&&KK(X(h[L+1])-X(h[L]),Y(h[L+1])-Y(h[L]),1,-s[i])>=0) ++L;
f[i]=g[h[L]]+(s[i]-s[h[L]])*s[h[L]]; p[j][i]=h[L];
while(L<R&&KK(X(h[R])-X(i),Y(h[R])-Y(i),X(h[R])-X(h[R-1]),Y(h[R])-Y(h[R-1]))<=0) --R;
h[++R]=i;
}swap(g,f);
}
printf("%lld\n",g[n]);//注意答案在g上
for(rint i=k,d=p[k][n];i;--i,d=p[i][d]) printf("%d ",d);
return 0;
}```

P3648 [APIO2014]序列分割（斜率优化dp）

(0)
(0)