题目描述
你正在玩一个关于长度为 nnn 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1k + 1k+1 个非空的块。为了得到 k+1k + 1k+1 块，你需要重复下面的操作 kkk 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
输入格式
第一行包含两个整数 nnn 和 kkk。保证 k+1≤nk + 1 \leq nk+1≤n。
第二行包含 nnn 个非负整数 a1,a2,??,ana_1, a_2, \cdots, a_na1?,a2?,?,an? (0≤ai≤104)(0 \leq a_i \leq 10^4)(0≤ai?≤104)，表示前文所述的序列。
输出格式
第一行输出你能获得的最大总得分。
第二行输出 kkk 个介于 111 到 n?1n - 1n?1 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 iii 个整数 sis_isi? 表示第 iii 次操作将在 sis_isi? 和 si+1s_{i + 1}si+1? 之间把块分开。
如果有多种方案使得总得分最大，输出任意一种方案即可。
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x*f;
}
const int N=1e5+10;
int a[N],q[N],pre[N][205],n,k;
ll s[N],f[N],g[N];
inline double shape(int i,int j){
if(s[i]==s[j])return -1e18;
return 1.0*((g[i]-s[i]*s[i])-(g[j]-s[j]*s[j]))/(s[j]-s[i]);
}
int main(){
n=read(),k=read(); for(int i=1;i<=n;i++)a[i]=read(),s[i]=s[i-1]+a[i];
for(int j=1;j<=k;j++){
int l=1,r=0; q[++r]=0;
for(int i=1;i<=n;i++){
while(l<r&&shape(q[l],q[l+1])<=s[i])l++;
f[i]=g[q[l]]+s[q[l]]*(s[i]-s[q[l]]);
pre[i][j]=q[l];
while(l<r&&shape(q[r-1],q[r])>=shape(q[r],i))r--;
q[++r]=i;
}
memcpy(g,f,sizeof(f));
}
printf("%lld\n",f[n]);
for(int x=n,i=k;i>=1;i--)x=pre[x][i],printf("%d ",x);
printf("\n");
}