「HNOI2018」题目整理

$HNOI$滚粗了,第一天还勉强苟住,第二天直接炸飞了,不管了。。。下面是一些题目的整理,动态规划还得巩固啊

道路

0x00 题意

给你一颗深度不超过 $40$ 的二叉树,对于每个非叶子节点 $u$,都有两个儿子节点

设一个叶子节点经过 $x$个有效的左儿子边,$y$个有效的右儿子边就可以到达根节点,那么这个节点的贡献为$w_i=c_i\times(a_i+x)\times(b_i+y)$

现在,对于每一个非叶子节点,你都可以选择其中一条通向自己儿子的边,使其失效,求最小的$\sum w_i$

0x01 我会暴力

显然,我们可以 $2^n$暴力枚举每个节点标记的是左儿子还是右儿子。。。然后每个点暴力向上跳,计算自己的贡献即可,时间复杂度 $O(n^22^n)$,实测可以获得20分的好成绩!

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
#include <bits/stdc++.h>
using namespace std;

const long long oo = 1e18;
const int maxn = 40001;
const int maxd = 41;

int s[maxn], t[maxn], f[maxn];
long long c[maxn], a[maxn], b[maxn];

template <typename Type>
inline Type read(Type u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

long long solve(int n) {
long long ans = oo;
for (register int sta = 0; sta < 1 << (n - 1); sta++) {
long long now = 0;
for (register int i = n + 1; i <= n << 1; i++) {
int u = i, x = 0, y = 0;
while (u != 1) {
int v = f[u];
x += u == s[v] && (sta & (1 << (v - 1)));
y += u == t[v] && !(sta & (1 << (v - 1)));
u = v;
} now += c[i - n] * (a[i - n] + x) * (b[i - n] + y);
if (now >= ans) break;
} ans = min(ans, now);
} return ans;
}

int main() {
int n = read<int>();
for (int i = 1; i < n; i++) {
s[i] = read<int>(); if (s[i] < 0) s[i] = n - s[i]; f[s[i]] = i;
t[i] = read<int>(); if (t[i] < 0) t[i] = n - t[i]; f[t[i]] = i;
}
for (int i = 1; i <= n; i++)
a[i] = read<long long>(),
b[i] = read<long long>(),
c[i] = read<long long>();
if (n <= 20) cout << solve(n) << endl;
}

0x02 我会模拟退火!

考虑到这相当于是一个含有$n$个变量的方程,要求一个极值的问题,我们可以利用模拟退火来处理。代码先不放了。。。

0x03 我会动态规划!

由于考场上智商直线下降。。。并没有搞出动态规划的做法。。。回头一想。。。天哪。。。傻逼题!

定义 $f[u][x][y]$表示,从节点$u$开始,向上还有$x$条有效的左儿子边,$y$条有效的右儿子边,子树中最少的和

不难发现以下转移方程,即两种决策,到底是使左儿子的边失效还是右儿子的边失效:
$$
f[u][x][y] = min\left\{ f[ls][x + 1][y] + f[rs][x][y], f[ls][x][y] + f[rs][x][y + 1] \right\}
$$
下面给出普及组难度的 $DP$ 代码,时间复杂度是 $O(nk^2)$ 的,其中 $k\leq40$,表示最大深度

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 40001;
const int maxd = 41;

int s[maxn], t[maxn];

long long c[maxn], a[maxn], b[maxn];
const long long oo = 1e18;
template <typename Type>
inline Type read(Type u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

void dfs(int u, long long f[41][41]) {
if (u < 0) {
for (int x = 0; x <= 40; x++)
for (int y = 0; y <= 40; y++)
f[x][y] = c[-u] * (a[-u] + x) * (b[-u] + y);
} else {
long long lf[41][41], rf[41][41];
dfs(s[u], lf); dfs(t[u], rf);
for (int x = 0; x <= 40; x++)
for (int y = 0; y <= 40; y++) {
f[x][y] = oo;
if (y <= 40) f[x][y] = min(f[x][y], lf[x][y] + rf[x][y + 1]);
if (x <= 40) f[x][y] = min(f[x][y], lf[x + 1][y] + rf[x][y]);
}
}
}

int main() {
int n = read<int>();
for (int i = 1; i < n; i++)
s[i] = read<int>(),
t[i] = read<int>();
for (int i = 1; i <= n; i++)
a[i] = read<long long>(),
b[i] = read<long long>(),
c[i] = read<long long>();
long long f[41][41];
memset(f, 0, sizeof(f));
dfs(1, f);
cout << f[0][0] << endl;
}