前言
题意简述
给你单调不降序列 \(\{a_n\}\)，你可以让 \(a_i \gets a_{i - 1} + a_{i + 1} - a_i\)，求操作后方差的最小值。
\(n \leq 10^4\)，\(1 \leq a_i \leq 600\)。
题目分析
仔细观察操作，发现实际上是将 \(a_i\) 按照 \(a_{i - 1}\) 和 \(a_{i + 1}\) 的中点 \(\dfrac{a_{i - 1} + a_{i + 1}}{2}\) 对称过去。
发现本质上是交换了 \(i - 1 \sim i\) 和 \(i \sim i + 1\) 的空隙，形式化地说，就是将 \(\{a_n\}\) 的差分数组 \(b_i = a_{i + 1} - a_i\) 交换了 \(b_i\) 和 \(b_{i - 1}\)。邻项交换，想到了什么？会不会和冒泡排序有关呢？我们发现，题目中并没有限制操作次数。再根据排序的性质，我们发现实际上我们可以将差分数组 \(\{b_n\}\) 任意重新排序！
一点说明：
差分数组是 \(n - 1\) 项，我们并不需要考虑 \(a_1 - a_0\)。因为我们只关心 \(a_i\) 的相对关系，而 \(a_1\) 决定 \(\{a_n\}\) 的绝对高度，你可以将 \(a_i \gets a_i - a_1\) 而不影响方差。
怎么重排差分数组来使方差尽量小呢？方差反映 \(\{a_n\}\) 的离散程度，我们需要让 \(a_i\) 尽量集中。经过打表找规律，我们发现，差分数组一定是一个单谷。yy 一下很显然，当然可以证明。
点击展开证明
首先方差 \(\operatorname{Var} \{a_n\} = \dfrac{1}{n} \sum \limits _ {i = 1} ^ n a_i^2 - \overline{a} ^ 2\)。
考虑 \(a_i \gets a_i + d\) 对 \(\operatorname{Var}\) 的影响为 \(\dfrac{1}{n}(d^2 + 2da_i) - \dfrac{1}{n^2}(d^2 + 2d\sum\limits_{j=1}^na_j)\)。
如果希望方差减少，那么 \(\dfrac{1}{n^2}(d^2 + 2d\sum\limits_{j=1}^na_j) \geq \dfrac{1}{n}(d^2 + 2da_i)\)，也就是 \(d^2 + 2d\sum\limits_{j=1}^na_j \geq d^2n + 2dna_i\)。
我们交换差分数组 \(d_{i-1}, d_i\)，会使 \(a_i \gets a_i + d_i - d_{i - 1}\)，此时 \(d = d_i - d_{i - 1}\)。我们讨论 \(d\) 的正负。
- \(d \gt 0\)，即 \(d_i > d_{i - 1}\)：
把上面不等式两边同时乘以 \(\dfrac{1}{nd}\)，得到需要 \(\dfrac{d}{n} + 2\overline{a} \geq d + 2a_i\) 才会使方差减少，移项一下是 \(\overline{a} - a_i \geq \dfrac{d}{2}(1 - \dfrac{1}{n}) \geq 0\)，所以要满足 \(a_i \leq \overline{a}\)。由于 \(a\) 不降，满足条件的是 \(a\) 的左侧一部分。操作到最终状态，不存在 \(d_i > d_{i - 1}\)，也就是 \(d_i \leq d_{i - 1}\)，此时方差最小。 - \(d \lt 0\)，即 \(d_i < d_{i - 1}\)：
同理得到如果 \(a_i \geq \overline{a}\)，最终 \(d_i \geq d_{i - 1}\)。
综合两种情况，差分数组 \(d\) 最终呈单谷时，方差最小。
知道 \(d\) 为单谷之后，要怎么求出最优的那个单谷呢？考虑 DP，从中间最小的开始，往两边扩展。也就是从小到大考虑 \(d_i\)，将其插在当前单谷左侧还是右侧。
状态肯定有 \(i\) 一维表示考虑前 \(i\) 个 \(d_i\)，记录的结果应该和方差有关。但是似乎不好转移，再加一维 \(j = \sum \limits _ {i = 1} ^ n a_i\)，那我们记录的 DP 值只用考虑 \(\sum \limits _ {i = 1} ^ n a_i ^ 2\)。也就是 \(f(i, j)\)。答案就是 \(\min \Big\{n \cdot f(n - 1, j) - j^2\Big\}\)，初始 \(f(0, 0) = 0\)。
转移分类讨论。
- 加在单谷左侧：\[f(i + 1, j + i \cdot d_i) \gets f(i, j) + 2j\cdot d_i + i \cdot d_i^2 \]
- 加在单谷右侧：
我们需要知道 \(\sum \limits _ {j = 1} ^ {i - 1} d_j\) 的值，不妨记作 \(s\)。\[f(i + 1, j + s) \gets f(i, j) + s^2 \]
滚一滚空间是 \(\Theta(nV)\)，但是时间 \(\Theta(nV^2)\) 不够。发现最后一个测试点 \(n >> V\)，说明有很多 \(d_i = 0\)，这不会对转移产生影响，所以可以跳过。优化到 \(\Theta(nV\min\{n,V\})\)。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
const int M = 500010;
using lint = long long;
const lint linf = 0x3f3f3f3f3f3f3f3f;
lint f[M];
int n, val[N], p[N], V;
inline void tomin(lint& a, lint b) {
b < a && (a = b);
}
signed main() {
#ifndef XuYueming
freopen("variance.in", "r", stdin);
freopen("variance.out", "w", stdout);
#endif
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &val[i]), V = max(V, val[i]);
for (int i = 1; i < n; ++i) p[i] = val[i + 1] - val[i];
sort(p + 1, p + n);
for (int i = 1; i < n; ++i) val[i] = val[i - 1] + p[i];
memset(f, 0x3f, sizeof (lint) * (n * V + 5));
f[0] = 0;
for (int i = 1, mx = 0; i < n; ++i) {
if (!p[i]) continue;
for (int j = mx; j >= 0; --j) {
if (f[j] == linf) continue;
tomin(f[j + i * p[i]], f[j] + 2ll * j * p[i] + 1ll * i * p[i] * p[i]);
tomin(f[j + val[i]], f[j] + 1ll * val[i] * val[i]);
mx = max(mx, j + i * p[i]);
mx = max(mx, j + val[i]);
f[j] = linf;
}
}
lint ans = linf;
for (int i = 0; i <= n * V; ++i) {
if (f[i] < linf)
ans = min(ans, n * f[i] - 1ll * i * i);
}
printf("%lld", ans);
return 0;
}