[文章目录]
Description
小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：
1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；
2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。
斜率优化。
1A啊！！！感觉爽死了。（为了犒劳自己买了杯奶茶233）
发现切的先后顺序并不影响贡献。所以可以dp。另外区间的贡献为所有分出来的小区间的和*每个区间的补集区间的和除以2。
先看朴素DP：设s[i]为1~i的a[i]的前缀和，sum为a[i]的总和。dp[i][k]表示1~i区间切成k段的最大收益。得到方程：
dp[i][j]=max(dp[k][j-1]+(s[i]-s[k])*(sum-s[i]+s[k]))
化简之后：dp[i][j]=max((2*s[k])*s[i]+(dp[k][j-1]-s[j]*sum-s[j]*s[j]))+s[i]*sum-s[i]*s[i]
可以斜率优化啊，不过队列中存的是上一个状态。
听旁边的EdwardFrog说他MLE了。。。那就写一维呗，在上维位算出来dp值的同时储存最优解，然后直接调用。初值注意一下。
然后，居然就切了！！！！！！爽死我了。。。赶紧喝了口奶茶233
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,kk;
ll dp[101000],k[101000],b[101000],qk[101000],qb[101000],s[101000],sum,ans;
int main()
{
scanf("%d%d",&n,&kk);
int i; ll x;
for(i=1;i<=n;++i)
{
scanf("%lld",&x);
s[i]=s[i-1]+x;
}
sum=s[n];
int j,h=1,t=1;
for(i=1;i<=n;++i)
{
dp[i]=s[i]*(sum-s[i]);
while(h<t&&qk[h]*s[i]+qb[h]<=qk[h+1]*s[i]+qb[h+1]) h++;
k[i]=qk[h]; b[i]=qb[h];
ll K=2*s[i],B=dp[i]-s[i]*(sum+s[i]);
while(h<t&&(B-qb[t])*(qk[t-1]-qk[t]) <= (qb[t]-qb[t-1])*(qk[t]-K)) t--;
qk[++t]=K; qb[t]=B;
}
for(j=2;j<=kk;++j)
{
h=1; t=1;
for(i=1;i!=j;++i) dp[i]=0;
for(i=j;i<=n;++i)
{
dp[i]=k[i]*s[i]+b[i]+s[i]*(sum-s[i]);
while(h<t&&qk[h]*s[i]+qb[h]<=qk[h+1]*s[i]+qb[h+1]) h++;
k[i]=qk[h]; b[i]=qb[h];
ll K=2*s[i],B=dp[i]-s[i]*(sum+s[i]);
while(h<t&&(B-qb[t])*(qk[t-1]-qk[t]) <= (qb[t]-qb[t-1])*(qk[t]-K)) t--;
qk[++t]=K; qb[t]=B;
}
}
for(i=1;i<=n;++i)
ans=max(ans,(dp[i]+(sum-s[i])*s[i])>>1);
printf("%lld\n",ans);
return 0;
}