P7962 [NOIP2021] 方差
给定长度为 \(n\) 的非严格递增正整数数列 \(1 \le a_1 \le a_2 \le \cdots \le a_n\)。每次可以进行的操作是：任意选择一个正整数 \(1 < i < n\)，将 \(a_i\) 变为 \(a_{i - 1} + a_{i + 1} - a_i\)。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 \(n^2\) 的结果。
其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 \(D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2\)，其中 \(\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i\)。
对于所有的数据，保证 \(1 \le n \le {10}^4\)， \(1 \le a_i \le 600\)。
答案化简为：
\[n \cdot \sum_{i=1}^n a_i^2 - \left(\sum_{i=1}^n a_i\right)^2\]
看一组数 \(a_1, a_2, \dots, a_n\)，对第 \(k\) 个数操作后变成 \(a'_k\)，而两组数的差分分别为 \(d_1, d_2, \dots, d_{n-1}\) 和 \(d'_1, d'_2, \dots, d'_{n-1}\)。
于是容易证明，该操作对数列的影响就是交换差分。
设 \(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} (n - i) d_i\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 \min\{j, k\} - j \cdot k) \\
&= \sum_{i=1}^{n-1} d_i^2 \cdot i \cdot (n - i) + 2 \sum_{1 \leq j < k \leq n-1} d_j \cdot d_k \cdot (n - j) \cdot k
\end{aligned}
\]
通过看最后一个式子可以看出答案最小时差分应该是呈现单谷，即答案最小时差分值先减后增。
所以可以考虑将所有差分从小到大排序后，然后设计一个动态规划决策每个差分值该放在单谷的左边还是右边。
转化过后的式子不好直接处理，还是用原先的式子较容易推导。
设 \(f(i, x)\) 表示已经考虑完前 \(i\) 个差分值，此时的 \(\sum_{j=1}^i (n - j) d_j\) 的和为 \(x\) 时最小的平方和，设 \(s_i = \sum_{j=1}^i d_j\)。
则现在要考虑 \(d_{i+1}\) 放在单谷的左边还是单谷的右边：
\[f(i, x) + 2 \cdot x \cdot d_{i+1} + i \cdot d_{i+1}^2 \rightarrow f(i+1, x + i \cdot d_{i+1})\]
\[f(i, x) + s_{i+1}^2 \rightarrow f(i+1, x + s_{i+1})\]
边界条件：
\[f(1, 0) = 0, \quad f(i, x) = +\infty \quad ((i, x) \neq (1, 0))\]
答案为：
\[\text{ans} = \min_{x} \left\{n \cdot f(n, x) - x^2\right\}\]
其中 \(x\) 为 \(\sum_{j=1}^{n-1} (n - j) d_j\) 中得到的最大的和。
考虑到所有差分值 \(d_i\) 非负，这个动态规划可以用类似背包的方法把第一维空间给优化掉，而第二维的范围是 \(O(n^2 \cdot a_i)\)，所以空间可以承受。
时间复杂度为 \(O(n^2 \cdot a_i)\)，通过优化后变为 \(O(n \cdot a_i)\)，可以通过。
注意要开 long long。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | #include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int MAXX = 5e5 + 10, MAXN = 1e5 + 10;
const ll inf = 1e12;
inline void chkmx(int &a, int b) { a = a < b ? b : a; }
inline void chkmn(int &a, int b) { a = a > b ? b : a; }
inline void chkmx(ll &a, ll b) { a = a < b ? b : a; }
inline void chkmn(ll &a, ll b) { a = a > b ? b : a; }
ll a[MAXN], d[MAXN], s[MAXN], f[MAXX], n, mx, mxa, ans = inf;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], d[i - 1] = a[i] - a[i - 1], chkmx(mxa, a[i]);
for (int i = 1; i <= mxa * n; i++)
f[i] = inf;
f[0] = s[0] = 0;
sort(d + 1, d + n);
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + d[i];
if (!d[i])
continue;
for (int j = mx; j >= 0; --j)
{
if (f[j] == inf)
continue;
chkmn(f[j + i * d[i]], f[j] + 2 * j * d[i] + i * d[i] * d[i]);
chkmn(f[j + s[i]], f[j] + s[i] * s[i]);
mx = max(mx, max(j + i * d[i], j + s[i]));
f[j] = inf;
}
}
for (int i = 0; i <= mx; i++)
if (f[i] < inf)
chkmn(ans, n * f[i] - 1ll * i * i);
cout << ans;
return 0;
}
|