【P7962 [NOIP2021] 方差】题解
MoYuFang
2021-11-25 08:04:01
本文起笔于```2021.11.25```。
[P7962 [NOIP2021] 方差](https://www.luogu.com.cn/problem/P7962)
答案化简为：
$$
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```。
```cpp
#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;
}
```