【P7962 [NOIP2021] 方差】题解

本文起笔于2021.11.25。

P7962 [NOIP2021] 方差

答案化简为：

n\cdot\sum_{i=1}^{n}a_i^2-\left(\sum_{i=1}^{n}a_i\right)^2

看一组数 a,b,c,d，对第而个数操作后变成 a,a+c-b,c,d，而两组数的差分分别为 b-a,c-b,d-c 和 c-b,b-a,d-c。

于是容易证明，该操作对数列的影响就是交换差分。

设 d_i=a_{(i+1)}-a_{i}，对答案做些变换：

\begin{aligned} n\cdot\sum_{i=1}^{n}a_i^2-\left(\sum_{i=1}^{n}a_i\right)^2 &=n\cdot\sum_{i=1}^{n}(a_i-a_1)^2-\left(\sum_{i=1}^{n}(a_i-a_1)\right)^2\\ &=n\cdot\sum_{i=1}^{n-1}\left(\sum_{j=1}^{i}d_j\right)^2-\left(\sum_{i=1}^{n-1}\sum_{j=1}^{i}d_j\right)^2\\ &=n\cdot\sum_{i=1}^{n-1}\sum_{j=1}^{i}\sum_{k=1}^{i}d_j\cdot d_k-\left(\sum_{j=1}^{n-1}d_j\cdot(n-j)\right)^2\\ &=n\cdot\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k\cdot(n-\max\{j,k\})-\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k\cdot(n-j)(n-k)\\ &=\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k\cdot(-n\cdot\max\{j,k\}+n\cdot(j+k)-j\cdot k)\\ &=\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}d_j\cdot d_k\cdot(n\cdot\min\{j,k\}-j\cdot k)\\ &= \sum_{i=1}^{n-1}d_i^2\cdot i\cdot(n-i)+ 2\sum_{j=1}^{n-1}\sum_{k=j+1}^{n-1}d_j\cdot d_k\cdot(n-j)\cdot k\\ \end{aligned}

通过看最后一个式子可以看出答案最小时差分应该是呈现单谷，即答案最小时差分值先减后增。

所以可以考虑将所有差分从小到大排序后，然后设计一个 \text{dp} 决策每个差分值该放在单谷的左边还是右边。

转化过后的式子不好 \text{dp}，还是用原先的式子较容易 \text{dp} 。

n\cdot\sum_{i=1}^{n}a_i^2-\left(\sum_{i=1}^{n}a_i\right)^2

设 f(i,x) 表示已经考虑完前 i-1 个差分值，此时的 a 的和为 x 时最小的平方和，设 s_i=\sum_{j=1}^{i}d_i 。

则现在要考虑 d_i 放在单谷的左边还是单谷的右边。

放左边：

f(i,x)+2\cdot x\cdot d_i + i\cdot d_i^2\rightarrow f(i+1,x+i\cdot d_i)

放右边：

f(i,x)+s_i^2\rightarrow f(i+1, x+s_i)

边界条件：

f(1,0)=0,\ \ f(i,x)=+\infty\ \ ((i,x)\neq(1,0))

答案为：

ans=\min_{x=0}^{mx}\{n\cdot f(n,x)-x^2\}

其中 mx 为 \text{dp} 中得到的最大的 a 的和。

考虑到所有差分值 d_i\geq 0 所以这个 \text{dp} 很容易用类似背包的方法把第一维空间给优化掉，而第二维的范围是 O(n\cdot a)，所以空间可以承受。

时间复杂度为 O(n\cdot n\cdot a)，这过不了。

再加一个小优化，考虑到 \min\{n,a\} 不会很大，所以 d_i 不为 0 的时刻不会很多，d_i 为 0 的时候不会发生任何转移，故可跳过，经过这一优化时间复杂度变成 O(\min\{n,a\}\cdot n\cdot a)，可以过。

注意要开 long long。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <assert.h>
using namespace std;

#define re register
#define sf scanf
#define pf printf
#define nl() putchar('\n')
#define ll long long
#define _for(i, a, b) for(re int (i) = (a); (i) < (b); ++(i))
#define _rfor(i, a, b) for(re int (i) = (a); (i) <= (b); ++(i))
#define inf 0x7ffffffffffffffll
#define maxn 10005
#define maxx 500005

int rdnt(){
    re int x = 0, sign = 1;
    re char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (c ^ 48), c = getchar();
    return x * sign;
}

ll  a[maxn], d[maxn], s[maxn], f[maxx];

inline void ud(re ll &x, re ll y){ if (y < x) x = y; }

int main(){
    #ifndef ONLINE_JUDGE
    freopen("variance.in", "r", stdin);
    freopen("variance.out", "w", stdout);
    #endif

    re int n = rdnt(), rg = 0; re ll mx = 0, ma = a[1] = rdnt();
    _rfor(i, 2, n) d[i-1] = (a[i] = rdnt())-a[i-1], ma = max(ma, a[i]);
    _rfor(x, 1, ma*n) f[x] = inf; f[0] = s[0]= 0;
    sort(d+1, d+n);
    _for(i, 1, n){
        s[i] = s[i-1] + d[i];
        if (d[i] == 0) continue;
        for(re int x = mx; x >= 0; --x){
            if (f[x] == inf) continue;
            ud(f[x+i*d[i]], f[x] + 2*x*d[i] + i*d[i]*d[i]);
            ud(f[x+s[i]], f[x] + s[i]*s[i]);
            mx = max(mx, max(x+i*d[i], x+s[i]));
            f[x] = inf;
        }
    }
    re ll ans = inf;
    _rfor(x, 0, mx) if (f[x] < inf) ud(ans, n*f[x] - (ll)x*x);
    pf("%lld\n", ans);

    return 0;
}