传送门
斜率优化dp经典题目。
首先需要证明只要选择的K个断点是相同的，那么得到的答案也是相同的。
根据分治的思想，我们只需要证明有两个断点时成立，就能推出K个断点时成立。
我们设两个断点分成的三段连续序列的和为a,b,ca,b,ca,b,c
如果先分左边有：total=a∗(b+c)+b∗c=a∗b+b∗c+c∗atotal=a*(b+c)+b*c=a*b+b*c+c*atotal=a∗(b+c)+b∗c=a∗b+b∗c+c∗a
如果先分右边有：total=(a+b)∗c+a∗b=a∗b+b∗c+c∗atotal=(a+b)*c+a*b=a*b+b*c+c*atotal=(a+b)∗c+a∗b=a∗b+b∗c+c∗a
是相同的。
那么这样我们就可以按从左到右划分断点的思路来进行dp了。
令f[i][j]f[i][j]f[i][j]为前j个数i个断点能够划分出的最大值。
那么显然有：
f[i]=maxf[i]=maxf[i]=max{f[j]+sum[j]∗(sum[i]−sum[j])f[j]+sum[j]*(sum[i]-sum[j])f[j]+sum[j]∗(sum[i]−sum[j])}
f[i]=maxf[i]=maxf[i]=max{f[j]−sum[j]2f[j]-sum[j]^2f[j]−sum[j]2}+sum[i]∗sum[j]+sum[i]*sum[j]+sum[i]∗sum[j]
if(k1<k2if(k1<k2if(k1<k2&&calc(k1)≤calc(k2))calc(k1)\le calc(k2))calc(k1)≤calc(k2))队头出队
=>f[k1]−sum[k1]2+sum[i]∗sum[k1]≤f[k2]−sum[k2]2+sum[i]∗sum[k2]f[k1]-sum[k1]^2+sum[i]*sum[k1]\le f[k2]-sum[k2]^2+sum[i]*sum[k2]f[k1]−sum[k1]2+sum[i]∗sum[k1]≤f[k2]−sum[k2]2+sum[i]∗sum[k2]
=>f[k1]−sum[k1]2−f[k2]+sum[k2]2≤(sum[k2]−sum[k1])∗sum[i]f[k1]-sum[k1]^2-f[k2]+sum[k2]^2\le (sum[k2]-sum[k1])*sum[i]f[k1]−sum[k1]2−f[k2]+sum[k2]2≤(sum[k2]−sum[k1])∗sum[i]
=>((f[k1]−sum[k1]2)−(f[k2]−sum[k2]2))/(sum[k2]−sum[k1]≤sum[i]((f[k1]-sum[k1]^2)-(f[k2]-sum[k2]^2))/(sum[k2]-sum[k1]\le sum[i]((f[k1]−sum[k1]2)−(f[k2]−sum[k2]2))/(sum[k2]−sum[k1]≤sum[i]
队尾出队：slope(q[tl−1],q[tl])>=slope(q[tl],i)slope(q[tl-1],q[tl])>=slope(q[tl],i)slope(q[tl−1],q[tl])>=slope(q[tl],i)
代码：
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,K,hd,tl,q[N],tmp;
ll f[2][N],sum[N];
inline ll calcX(int i,int j){return sum[j]-sum[i];}
inline ll calcY(int i,int j){return (f[tmp^1][i]-sum[i]*sum[i])-(f[tmp^1][j]-sum[j]*sum[j]);}
int main(){
n=read(),K=read(),tmp=0;
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+read();
for(int i=1;i<=K;++i){
hd=tl=1;
for(int j=1;j<=n;++j){
while(hd<tl&&calcY(q[hd],q[hd+1])<=calcX(q[hd],q[hd+1])*sum[j])++hd;
int k=q[hd];
f[tmp][j]=f[tmp^1][k]+sum[k]*(sum[j]-sum[k]);
while(hd<tl&&calcY(q[tl-1],q[tl])*calcX(q[tl],j)>=calcY(q[tl],j)*calcX(q[tl-1],q[tl]))--tl;
q[++tl]=j;
}
tmp^=1;
}
printf("%lld",f[tmp^1][n]);
return 0;
}