此题我看到第一眼的想法是
区间DP，复杂度大约O(n^4)
但是我在推样例的时候发现了一个重要的性质
最后的结果只与切的位置有关而与切的顺序无关
将状态设计为f[i][j]表示前i个数，切j刀，第j刀切在i处所最得到的最大的分
由此我们可以推出DP式子：f[i][k+1]=f[j][k]+sum[j]*(sum[i]-sum[j]);
但这样的复杂度仍然不对
看到式子的形状，我们似乎可以采用斜率优化
f[j][k]-sum[j]*sum[j]=f[i][k+1]-sum[i]*sum[j];
这里我们要注意两个点在同一个横坐标的情况
另外我们只用开一个队列Q
因为虽然转移得到的截距为k+1的，但是点(x,y)都是k的
实现如下：
#include <algorithm> #include <iostream> #include <cmath> #include <cstring> #include <map> #include <string> #include <vector> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> using namespace std; typedef long long ll; inline ll read() { register ll p(1),a(0);register char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if(ch=='-') p=-1,ch=getchar(); while(ch>='0'&&ch<='9') a=a*10+ch-48,ch=getchar(); return a*p; } //f[i][k]=f[j][k-1]+sum[j]*(sum[i]-sum[j]); //f[j][k-1]-sum[j]*sum[j]=f[i][k]-sum[i]*sum[j]; const ll N=100100,M=210,INF=0x3f3f3f3f; ll n,kk,f[N][M],to[N][M],sum[N],Q[N],head=0,tail=0; inline long double getx(int x){return sum[x];} inline long double gety(int x,int now){return f[x][now]-sum[x]*sum[x];} inline long double che(int x,int y,int now) {return getx(y)==getx(x)?-INF:(gety(y,now)-gety(x,now))/(getx(x)-getx(y));} inline void pri(int xx,int yy){if(xx)pri(to[xx][yy],yy-1),printf("%lld ",xx);} int main() { freopen("input","r",stdin); freopen("output","w",stdout); n=read(),kk=read(); for(register int i=1;i<=n;i++) sum[i]=sum[i-1]+read(); for(register int k=1;k<=kk;k++,head=tail=0) for(register int i=1,j;i<=n;i++) { while(head<tail&&che(Q[head],Q[head+1],k)<=sum[i]) ++head; j=Q[head];f[i][k+1]=f[j][k]+sum[j]*(sum[i]-sum[j]); to[i][k+1]=j; while(head<tail&&che(Q[tail-1],Q[tail],k)>=che(Q[tail],i,k)) --tail; Q[++tail]=i; } printf("%lld ",f[n][kk+1]); pri(to[n][kk+1],kk); return 0; } /* */