目录
显示
题目链接
https://www.luogu.com.cn/problem/P4072
题解
先玩玩方差公式：
$$s^2=\sum_{i=1}^m \frac{(x_i-\bar{x})^2}{m}$$
先按照题目要求给两边同时乘个 \(m^2\)：
$$\begin{align*} m^2 \times s^2 &= m\sum_{i=1}^m (x_i-\bar{x})^2\\ &= m\sum_{i=1}^m x_i^2-2x_i\bar{x}+\bar{x}^2\\ &= m(\sum_{i=1}^m x_i^2-2\bar{x}\sum_{i=1}^m x_i+m\bar{x}^2)\\ &= m\sum_{i=1}^m x_i^2-(\sum_{i=1}^m x_i)^2\\ \end{align*}$$
结果的第二部分显然是个定值，所以我们的目标是让第一部分（平方和）最小。
设 \(f_{i,j}\) 表示前 \(i\) 个数分为 \(j\) 段的平方和最小值。
设前缀和为 \(s_i\)，则显然有：
$$f_{i,j}=\min f_{p,j-1}+(s_j-s_p)^2$$
暴力转移时间复杂度为 \(O(n^2m)\)。
考虑上斜率优化。
设 \(j>k\) 且 \(j\) 处决策更优，同时记 \(f_i=f_{i,j}\)，\(g_i=f_{i,j-1}\)，则有：
$$\frac{g_j-g_k+s_j^2-s_k^2}{s_j-s_k}\lt 2s_i$$
#include <cstring>
#include <iostream>
using namespace std;
int s[3005],f[3005],g[3005],q[3005];
double slope(int x,int y)
{
return 1.0*(g[x]-g[y]+s[x]*s[x]-s[y]*s[y])/(s[x]-s[y]);
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]+=s[i-1];
g[i]=s[i]*s[i];
}
for(int p=1;p<m;p++)
{
memset(q,0,sizeof(q));
int l=0,r=0;
for(int i=1;i<=n;i++)
{
while(l<r&&slope(q[l],q[l+1])<2*s[i])
l++;
int x=s[i]-s[q[l]];
f[i]=g[q[l]]+x*x;
while(l<r&&slope(q[r-1],q[r])>slope(q[r],i))
r--;
q[++r]=i;
}
memcpy(g,f,sizeof(g));
}
cout<<f[n]*m-s[n]*s[n]<<endl;
return 0;
}