首先看这个得分方式，容易发现就相当于分k段，每段的值和两两乘起来。
这样就很容易列出dp方程：设f[i][j]为到j分成分成i段，转移是
\[f[i][j]=max { f[k][j]+s[k]*(s[j]-s[k]) }
\]
\]
然后显然这个可以斜率优化，随便推一推式子，假设k选p大于选q，那么
\[f[p][j]+s[p]*(s[j]-s[p])>f[q][j]+s[q]*(s[j]-s[q])
\]
\]
\[f[p][j]+s[p]*s[j]-s[p]^2>f[q][j]+s[q]*s[j]-s[q]^2
\]
\]
\[f[p][j]-f[q][j]-s[p]^2+s[q]^2>s[j]*(s[q]-s[p])
\]
\]
\[\frac{f[p][j]-f[q][j]-s[p]^2+s[q]^2}{s[q]-s[p]}>s[j]
\]
\]
维护一个斜率单调的队列即可。
注意s[q]-s[p]可能是0，所以要特判一下
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,to[205][N],q[N];
long long s[N],f[2][N];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
inline double wk(int r,int j,int k)
{
if(s[j]==s[k])
return -1e18;
return (f[r&1^1][k]-s[k]*s[k]-f[r&1^1][j]+s[j]*s[j])*1.0/(s[j]-s[k]);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
s[i]=s[i-1]+read();
for(int i=1;i<=m;i++)
{
int l=0,r=0;
for(int j=1;j<=n;j++)
{
while(l<r&&wk(i,q[l],q[l+1])<=s[j])
l++;
to[i][j]=q[l];
f[i&1][j]=f[(i&1)^1][q[l]]+s[q[l]]*(s[j]-s[q[l]]);
while(l<r&&wk(i,q[r-1],q[r])>=wk(i,q[r],j))
r--;
q[++r]=j;
}
}
printf("%lld\n",f[m&1][n]);
for(int i=m,u=n;i>=1;i--)
{
u=to[i][u];
printf("%d ",u);
}
return 0;
}#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,to[205][N],q[N];
long long s[N],f[2][N];
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
inline double wk(int r,int j,int k)
{
if(s[j]==s[k])
return -1e18;
return (f[r&1^1][k]-s[k]*s[k]-f[r&1^1][j]+s[j]*s[j])*1.0/(s[j]-s[k]);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
s[i]=s[i-1]+read();
for(int i=1;i<=m;i++)
{
int l=0,r=0;
for(int j=1;j<=n;j++)
{
while(l<r&&wk(i,q[l],q[l+1])<=s[j])
l++;
to[i][j]=q[l];
f[i&1][j]=f[(i&1)^1][q[l]]+s[q[l]]*(s[j]-s[q[l]]);
while(l<r&&wk(i,q[r-1],q[r])>=wk(i,q[r],j))
r--;
q[++r]=j;
}
}
printf("%lld\n",f[m&1][n]);
for(int i=m,u=n;i>=1;i--)
{
u=to[i][u];
printf("%d ",u);
}
return 0;
}