P7962 [NOIP2021] 方差
小清新DP。
手玩发现操作本质是交换差分序列的相邻两项。这个序列同时加减相同的数，方差不变，因此答案只和差分序列有关。继续挖掘性质，可以发现答案中差分序列的是呈单谷函数的。将差分序列按照从小到大排序，每次考虑将一个新的数插入在序列左侧或者右侧，推式子 $n \sum _ {i = 1} ^ n a _ i ^ 2 - (\sum _ {i = 1} ^ n a _ i) ^ 2$ ，DP 维护所有数的和一定时平方和的最小值。最后取最小值即可。
注意到 $n > \max (a_ i) $ 时会存在 $0$ ，将这些 $0$ 去掉，不再需要做 $O(n)$ 次，只需 $O(\min(n, \max(a _ i)))$ 次。
查看代码
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0';
flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e4 + 10, M = 5e5 + 10;
const LL inf = 1e15;
int n, m, w[N], s[N];
LL f[2][M];
void chkmin (LL &x, LL k) { if (k < x) x = k; }
int main ()
{
read(n);
for (int i = 1; i <= n; ++i) read(w[i]);
m = w[n] * n; --n;
for (int i = 1; i <= n; ++i) w[i] = w[i + 1] - w[i];
sort(w + 1, w + n + 1);
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + w[i];
int op = 0;
f[op][0] = 0;
for (int i = 1; i <= m; ++i) f[op][i] = inf;
for (int i = 1; i <= n; ++i) if (w[i])
{
op ^= 1;
for (int j = 0; j <= m; ++j) f[op][j] = inf;
for (int j = 0; j <= m; ++j) if (f[op ^ 1][j] ^ inf)
{
chkmin(f[op][j + s[i]], f[op ^ 1][j] + s[i] * s[i]);
chkmin(f[op][j + w[i] * i], f[op ^ 1][j] + 2 * j * w[i] + w[i] * w[i] * i);
}
}
LL res = inf;
for (int i = 0; i <= m; ++i) if (f[op][i] ^ inf)
chkmin(res, (n + 1) * f[op][i] - (LL)i * i);
write(res);
return 0;
}
|