# Google Kick Start 2019 Round F 题解

# Problem A - Flattening

# 题目描述

$n=8,k=2$

$a=[300,100,300,300,200,100,800,500]$

• $a_2$ 100->300
• $a_6$ 100->200
• $a_7$ 800->200

# 题解

$f[i][j][m]=\min(f[i-1][j][m], minf[i-1][j-1]) + (a[i] != nums[m])$

$f[i-1][j][m]$ 的情况，由于上一个数字是 $nums[m]$，和当前增加的这个数字一样，所以不会增加不一致的对数。 $minf[i-1][j-1]$ 的情况，不管取得最小值时的最后一个数字是什么，至多增加一对不一致的对数，所以不一致对数不会超过 $j$

#include <algorithm>
#include <climits>
#include <iostream>
#include <unordered_set>
#include <vector>

typedef long long ll;

using namespace std;

void solve(int case_num) {
int n, k;
cin >> n >> k;
vector<ll> a;
unordered_set<ll> nums_set;
for (int i = 0; i < n; ++i) {
int ai;
cin >> ai;
a.emplace_back(ai);
nums_set.insert(ai);
}
vector<ll> nums(nums_set.begin(), nums_set.end());
int t = nums.size();

vector<vector<vector<ll>>> f(
n + 1, vector<vector<ll>>(k + 1, vector<ll>(t, INT_MAX)));
vector<vector<ll>> minf(n + 1, vector<ll>(k + 1, INT_MAX));

for (int i = 0; i < t; ++i) {
if (nums[i] != a[0]) {
f[1][0][i] = 1;
} else {
f[1][0][i] = 0;
minf[1][0] = 0;
}
}

for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= min(k, i - 1); ++j) {
for (int m = 0; m < t; ++m) {
f[i][j][m] = f[i - 1][j][m];
if (j > 0)
f[i][j][m] = min(f[i][j][m], minf[i - 1][j - 1]);
if (a[i - 1] != nums[m])
f[i][j][m]++;
if (f[i][j][m] < minf[i][j])
minf[i][j] = f[i][j][m];
}
}
}

ll ans = INT_MAX;
for (int j = 0; j <= k; ++j)
for (int m = 0; m < t; ++m)
ans = min(ans, f[n][j][m]);

cout << "Case #" << case_num << ": " << ans << endl;
}

int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
}
return 0;
}

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
58
59
60
61
62
63
64
65
66
67

# Problem B - Teach Me

# 题解

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
const ll radix = 1001;

void solve(int case_num) {
int n, s;
cin >> n >> s;
vector<ll> a;
unordered_map<ll, int> cnt;
for (int i = 0; i < n; ++i) {
int skill_count;
cin >> skill_count;
vector<int> skills(skill_count);
for (int j = 0; j < skill_count; ++j)
scanf("%d", &skills[j]);
sort(skills.begin(), skills.end());
ll hash = 0;
for (const int &skill : skills)
hash = hash * radix + skill;
a.emplace_back(hash);
for (int j = 0; j < (1 << skill_count); ++j) {
ll hash = 0;
for (int k = 0; k < skill_count; ++k)
if (j & (1 << k))
hash = hash * radix + skills[k];
cnt[hash]++;
}
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
ans += n - cnt[a[i]];
}
cout << "Case #" << case_num << ": " << ans << endl;
}

int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
}
return 0;
}

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

# Problem C - Spectating Villages

# 题目描述

$n$ 个村子由 $n-1$ 条无向边连接，保证任意两个村子可达（也即构成一棵树）。每个村子有一盏灯，一个村子点亮灯之后，所有相邻的村子也会被照亮。每个村子有一个美观值 $b_i$$-10^5\leq b_i\leq 10^5$）。现在可以点亮任意多盏灯（也可以一盏都不点亮），求所有被照亮的村子的美观值总和的最大值。

# 题解

• 对于叶子节点，只有点灯、不点灯两种情况。
• 对于非叶子节点，有点灯、不点灯且不被点亮、不点灯但被点亮（也即至少一个孩子节点点灯）三种情况。

• $f[i][0]=\sum_{j\in adj[i]} \max(f[j][0], f[j][2])$
• $f[i][1]=\sum_{j\in adj[i]} \max(f[j][0], f[j][1] - b_j, f[j][2] - b_j)+b_j$
• $f[i][2]$ 稍微复杂一些，需要比较所有的 $\max(f[j][0], f[j][2])$$f[j][1]$。如果存在 $f[j][1]\leq\max(f[j][0], f[j][2])$，那么直接取总和即可；否则需要用与对应的 $\max(f[j][0], f[j][2])$ 差距最小的 $f[j][1]$ 去替换，这样才能保证至少有一个孩子节点的灯是亮的，从而当前节点是被照亮的。

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

typedef long long ll;

using namespace std;

class Graph {
vector<ll> val, parent;

void dfs(int u, int fa) {
int d = adj[u].size();
for (int i = 0; i < d; i++) {
int v = adj[u][i];
if (v != fa)
dfs(v, parent[v] = u);
}
}

void to_tree() {
parent = vector<ll>(val.size());
parent[0] = -1;
dfs(0, -1);
for (int i = 0; i < val.size(); ++i)
for (int i = 1; i < val.size(); ++i) {
}
}

void traverse(int u) {
f[u][0] = 0;
f[u][1] = val[u];
f[u][2] = INT_MIN;
} else {
f[u][0] = 0;
for (const int j : adj[u]) {
traverse(j);
f[u][0] += max(f[j][0], f[j][2]);
}
bool open = false;
ll sec = 0;
for (const int j : adj[u]) {
ll m = max(f[j][0], f[j][2]);
sec += max(m, f[j][1]);
if (f[j][1] >= m)
open = true;
}
if (!open) {
ll delta = INT_MAX;
for (const int j : adj[u]) {
delta = min(delta, max(f[j][0], f[j][2]) - f[j][1]);
}
sec -= delta;
}
f[u][2] = sec + val[u];

f[u][1] = val[u];
for (const int j : adj[u]) {
f[u][1] += max(f[j][0], max(f[j][1], f[j][2]) - val[j]) + val[j];
}
}
}

public:
Graph(vector<ll> &a) {
val = vector<ll>(a);
adj = vector<vector<ll>>(a.size(), vector<ll>{});
}

void add_edge(int a, int b) {
}

ll best() {
to_tree();
f = vector<vector<ll>>(val.size(), vector<ll>(3));
traverse(0);
return max(f[0][0], max(f[0][1], f[0][2]));
}
};

void solve(int case_num) {
int v;
cin >> v;
vector<ll> val;
for (int i = 0; i < v; ++i) {
int vi;
cin >> vi;
val.emplace_back(vi);
}
Graph g = Graph(val);
for (int i = 0; i < v - 1; ++i) {
int a, b;
cin >> a >> b;
g.add_edge(a - 1, b - 1);
}

cout << "Case #" << case_num << ": " << g.best() << endl;
}

int main() {
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {

solve(i);
}
return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114