[洛谷 4072,loj 2035][SDOI2016]征途

题目链接

https://www.luogu.com.cn/problem/P4072

https://loj.ac/problem/2035

题解

先玩玩方差公式:

$$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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据