洛谷4072 [SDOI2016]征途

题意

把 $N$ 个数分成 $M$ 段，要求每段和的方差尽可能小，求最小值。

$N\le 3000$ 。

题解

我这个辣鸡的错误解法

方程还是比较容易想到的，用 $f[i][j]$ 表示当前是第 $i$ 段，分到第 $j$ 个数的最优解，方程为：

$$f[i][j] = \min_{k=0}^{j-1} (f[i-1][k] + \sum_{p=k+1}^j M\times (X_p - \overline {X})^2)$$

然后我就硬着头皮继续化简。因为 $\times M^2$ 后把每一项拆出来还是可能出现非整数，所以我就再 $\times M$ ，最后除掉就行了。

看起来有 $i$ 和 $j$ 相乘的项，所以往斜率优化去化简。用 $S_i$ 代表 $X_i$ 的前缀和，最后我写了两张草稿纸后得到了个又长又丑的式子：

$$M^2\times {S_k}^2 + f[i-1][k] = (2\times M^2\times S_j-w\times M\times S_n)\times S_k + (f[i][j]-M^2\times {S_j}^2 + 2\times M\times S_n\times S_j - {S_n}^2)$$

然后我悲催的发现 $(2\times M^2\times S_j-w\times M\times S_n)$ 虽然满足单调性，但可能是负的，不能用斜率优化，$GG$ 。

正解

$s^2$ 表示方差，$V_i$ 表示每一段的和，则

$$s^2M^2 = M\sum_{i=1}^M V_i^2-(\sum_{i=1}^mV_i)^2$$

可以发现 $(\sum_{i=1}^mV_i)^2$ 是固定的，所以最小化 $\sum_{i=1}^M V_i^2$ 就行了。直接上方程：

$$f[i][j] = \min_{k=1}^{j-1} (f[i-1][k] + (S_j-S_k)^2)$$

$$f[i-1][k] + {S_k}^2 = 2S_j\times S_k + (f[i][j]-{S_j}^2)$$

斜率 $2S_j$ 递增。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,p,sum,s[3005],f[3005][3005],q[3005];

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) s[i]=s[i-1]+read();
    for (int i=1;i<=n;i++) f[1][i]=s[i]*s[i];
    for (int i=2;i<=m;i++)
    {
        int l=1,r=1; q[l]=0;
        for (int j=1;j<=n;j++)
        {
            while (l<r && f[i-1][q[l+1]]+s[q[l+1]]*s[q[l+1]]-f[i-1][q[l]]-s[q[l]]*s[q[l]]
                   <=(s[q[l+1]]-s[q[l]])*2*s[j]) l++;
            f[i][j]=f[i-1][q[l]]+(s[j]-s[q[l]])*(s[j]-s[q[l]]);
            while (l<r && (f[i-1][q[r]]+s[q[r]]*s[q[r]]-f[i-1][q[r-1]]-s[q[r-1]]*s[q[r-1]])*(s[j]-s[q[r]])
                   >=((f[i-1][j]+s[j]*s[j]-f[i-1][q[r]])-s[q[r]]*s[q[r]])*(s[q[r]]-s[q[r-1]])) r--;
            q[++r]=j;
        }
    }
    return !printf("%d",m*f[m][n]-s[n]*s[n]);
}