目录
显示
题目链接
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; }