自动搬运

查看原文

来自洛谷，原作者为

	MoYuFang AFO

搬运于2025-08-24 22:34:42，当前版本为作者最后更新于2021-11-25 08:04:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本文起笔于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;
}