Description：

把 $n$ 个数划分成 $m$ 段，最小化方差乘 $m^2$ 的值。

$1\le n \le 3000$

Solution：

先把方差拆开： $\begin{align}s=m\sum_{i=1}^m (s_i-\bar x)^2=m\sum_{i=1}^ms_i^2-(\sum_{i=1}^ms_i)^2\end{align}$ ，只要最小化 $\begin{align}m\sum_{i=1}^ms_i^2\end{align}$ 就行了。

这个可以 $DP$ 做，转移为 $f[i][k]=\min(f[j][k-1]+m\times (sum[i]-sum[j])\times(sum[i]-sum[j]))$ ，可以斜率优化， $f[j]][k-1]+m\times sum[j]\times sum[j]=2\times m\times sum[i]\times sum[j]+f[i][k]-m\times sum[i]\times sum[i]$ 。

$x=sum[j]$ 单调递增， $k=2\times m\times sum[i]$ 单调递增，要维护下凸壳，单调队列即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 3010

typedef long long ll;

ll a[MAXN];

ll sum[MAXN];

ll f[MAXN][MAXN];

int q[MAXN],head,tail;

int x(int p){return sum[p];}

int y(int p,int k){return f[p][k - 1] + m * sum[p] * sum[p];}

double slope(int a,int b,int k){return (y(a,k) - y(b,k)) / (x(a) - x(b));}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + a[i];

	memset(f,0x3f,sizeof(f));

	f[0][0] = 0;

	for(int k = 1;k <= m;++k)

	{

		head = 1;tail = 0;q[++tail] = 0;

		for(int i = 1;i <= n;++i)

		{

			while(head < tail && slope(q[head],q[head + 1],k) < 2 * m * sum[i])++head;

			f[i][k] = f[q[head]][k - 1] + m * sum[i] * sum[i] - 2 * m * sum[i] * sum[q[head]] + m * sum[q[head]] * sum[q[head]];

			while(head < tail && slope(q[tail - 1],q[tail],k) > slope(q[tail],i,k))--tail;

			q[++tail] = i;

		}

	}

	int ans = f[n][m] - sum[n] * sum[n];

	cout << ans << endl;

	return 0;

}