本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000作者博客：
转载请注明出处，侵权必究，保留最终解释权！
题目链接：
正解：DP+斜率优化
解题报告：
容易发现，答案只和分割处有关，与顺序无关。
所以朴素方程很容易得到：
令${S[n]=\sum_{i=1}^{n}a[i]}$
${f[i][k]=max(f[j][k-1]+S[j]*(S[i]-S[j])) ,j<i}$
对于${j1,j2}$且满足${j1<j2}$，${f[j1][k-1]<f[j2][k-1]}$，显然$j1$可以被删除，则
${f[j1][k-1]+S[j1]*(S[i]-S[j1]) < f[j2][k-1]+S[j2]*(S[i]-S[j2])}$
化简后：
${f[j1][k-1]-f[j2][k-1]+S[j2]^2-S[j1]^2 > S[i]*(S[j2]-S[j1])}$
令${g[i][k]=f[i][k]-S[i]^2}$
则${g[j1][k-1]-g[j2][k-1]>S[i]*(S[j2]-S[j1])}$
到了这一步，正解就已经呼之欲出了。显然我们可以用斜率优化+单调队列，把DP优化到$O(nk)$，做k次，每次只需扫一遍。
队首如果满足上式，则直接删掉。加入队尾的时候，，看一下斜率的变化趋势，如果不满足则pop掉。
//It is made by ljh2000 #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <complex> using namespace std; typedef long long LL; const int MAXN = 100011; int n,k,dui[MAXN],head,tail; LL g[MAXN],s[MAXN],f[MAXN],F[MAXN]; int ans[MAXN],pre[MAXN][211]; inline int getint(){ int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } inline LL calc(int i,int j1,int j2){ return s[i]*(s[j2]-s[j1]); } inline void work(){ n=getint(); k=getint(); for(int i=1;i<=n;i++) s[i]=getint(); for(int i=2;i<=n;i++) s[i]+=s[i-1]; for(int i=1;i<=n;i++) g[i]=-s[i]*s[i]; for(int nowk=2;nowk<=k+1;nowk++) { head=tail=0; dui[++tail]=nowk-1; for(int i=nowk;i<=n;i++) { while(head<tail && calc(i,dui[head],dui[head+1])>=(g[dui[head]]-g[dui[head+1]])) head++; F[i]=f[dui[head]]+s[dui[head]]*(s[i]-s[dui[head]]); pre[i][nowk-1]=dui[head]; while(head<tail && (g[dui[tail-1]]-g[dui[tail]])*(s[i]-s[dui[tail]]) >= (g[dui[tail]]-g[i])*(s[dui[tail]]-s[dui[tail-1]])) tail--; dui[++tail]=i; } for(int i=nowk;i<=n;i++) f[i]=F[i],g[i]=F[i]-s[i]*s[i]; } printf("%lld\n",F[n]); for(int i=n,j=k;i>0;j--) i=pre[i][j],ans[j]=i; for(int i=1;i<=k;i++) printf("%d ",ans[i]); } int main() { work(); return 0; }
UOJ104 【APIO2014】Split the sequence