%%%%%
by Konnyaku_LXZ @ 2020-10-01 20:39:39
%%%%%
by chen_03 @ 2020-10-01 20:41:13
没发现宁的代码有什么错的
放一个我的代码吧QAQ
```
#include<stdio.h>
#define int long long
#define inf 100000000000000000
const int maxn=3005,maxm=3005;
int i,j,k,m,n;
int a[maxn],sum[maxn],f[maxm][maxn],q[maxn];
inline int x(int p){
return sum[p];
}
inline int y(int p,int c){
return f[c-1][p]+sum[p]*sum[p];
}
inline double slope(int a,int b,int c){
if(x(a)==x(b))
return y(a,c)>y(b,c)? inf:-inf;
return 1.0*(y(a,c)-y(b,c))/(x(a)-x(b));
}
signed main(){
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(i=1;i<=n;i++)
f[0][i]=inf;
for(i=1;i<=m;i++){
int l=1,r=0;
q[++r]=0;
for(j=1;j<=n;j++){
while(l<r&&slope(q[l+1],q[l],i)<=2.0*sum[j])
l++;
f[i][j]=f[i-1][q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
while(l<r&&slope(j,q[r-1],i)<=slope(q[r],q[r-1],i))
r--;
q[++r]=j;
}
}
printf("%lld\n",m*f[m][n]-sum[n]*sum[n]);
return 0;
}
```
by whiteqwq @ 2020-10-01 20:59:02
我也90分……
by walk_alone @ 2021-02-25 21:38:57
@[yama是女孩子](/user/261947) 那个 `q[1]=k` 应该是 `q[1]=k-1` 吧
by HPXXZYY @ 2022-02-10 13:32:42
for (int k = 1 ; k < m ; k++)
by 2021AC @ 2022-02-25 12:10:44