首先根据题目中给的要求，推一下方差的柿子。
[v imes m^2 = m imes sum x^2 - 2 imes sum imes sum +sum*sum
]
所以(ans = v*m^2 = m imes sum x^2 - sum*sum)
那我们实际上就是最大化平方和。
由于题目限制了要分(m)段。所以我们的(dp)状态就是(f[i][j])表示前(i)个数分了(j)段。
那么一个比较显然的转移
(dp[i][p]=min(dp[j][p-1]+(s[i]-s[j]^2)))
然后直接套斜率优化就好了！
但是要注意的是，因为题目中对第二维有点限制，所以我们要开(m)个单调队列来维护。
对于(dp[i][j])，每次从(j-1)的单调队列要转移。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define mk make_pair
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 3010;
struct Point{
int x,y;
};
ll chacheng(Point x,Point y)
{
ll xx = x.x;
ll yy = x.y;
ll xxx = y.x;
ll yyy = y.y;
return xx*yyy-xxx*yy;
}
struct Node{
Point q[maxn];
int head=1,tail=0;
bool count(Point i,Point j,Point k)
{
Point x,y;
x.x=k.x-i.x;
x.y=k.y-i.y;
y.x=k.x-j.x;
y.y=k.y-j.y;
if (chacheng(x,y)<=0ll) return true;
return false;
}
void push(Point x)
{
while (tail>=head+1 && count(q[tail-1],q[tail],x)) tail--;
q[++tail]=x;
}
void pop(int lim)
{
while (tail>=head+1 && q[head+1].y-q[head].y<lim*(q[head+1].x-q[head].x)) head++;
}
};
Node q[maxn];
int sum[maxn];
int n,m;
int dp[maxn][maxn];
int main()
{
n=read();m=read();
for (int i=1;i<=n;i++) sum[i]=read();
for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
for (int i=0;i<=n;i++) q[i].push((Point){0,0});
for (int i=1;i<=n;i++)
{
for (int j=1;j<=min(i,m);j++)
{
q[j-1].pop(2*sum[i]);
Point now = q[j-1].q[q[j-1].head];
dp[i][j]=now.y-now.x*now.x + (sum[i]-now.x)*(sum[i]-now.x);
q[j].push((Point){sum[i],dp[i][j]+sum[i]*sum[i]});
}
}
//cout<<dp[n][m]<<" "<<m<<" "<<sum[n]*sum[n]<<endl;
cout<<dp[n][m]*m-sum[n]*sum[n]<<endl;
return 0;
}