RenaMoe's Blog

念念不忘，必有回响

0%

题解 P2279 【[HNOI2003]消防局的设立】

发表于 更新于 分类于 ， Valine：

题目

第一道连状态都不会表示的\(dp\)

转移方程推到吐。。。

状态表示

每一个点\(x\)都有五个状态：

f[x][0]：覆盖到x的爷爷和x整棵子树（向上2层），最少个数

f[x][1]：覆盖到x的父亲和x整棵子树（向上1层），最少个数

f[x][2]：覆盖x整棵子树（向上0层），最少个数

f[x][3]：覆盖所有x的儿子及其子树（向上-1层），最少个数

f[x][4]：覆盖所有x的孙子及其子树（向上-2层），最少个数

  • f[x][0]：覆盖到x的爷爷和x整棵子树（向上2层），最少个数

  • f[x][1]：覆盖到x的父亲和x整棵子树（向上1层），最少个数

  • f[x][2]：覆盖x整棵子树（向上0层），最少个数

  • f[x][3]：覆盖所有x的儿子及其子树（向上-1层），最少个数

  • f[x][4]：覆盖所有x的孙子及其子树（向上-2层），最少个数

转移方程

y，z是x的儿子

\(f[x][0] = 1 + \sum{f[y][4]}\) \(f[x][1] = min(f[y][0] + \sum{(y!=z)f[z][3]})\) \(f[x][2] = min(f[y][1] + \sum{(y!=z)f[z][2]})\) \(f[x][3] = \sum{f[y][2]}\) \(f[x][4] = \sum{f[y][3]}\)

显然f[x][i]一定包含f[x][i+1]

易得f[x][0] >= f[x][1] >= f[x][2] >= f[x][3] >= f[x][4]

所以转移时保证满足条件的前提下尽量选最低层的状态

  • \(f[x][0] = 1 + \sum{f[y][4]}\)

要覆盖到爷爷的话必须选x，并贪心地选y的第五种状态

  • \(f[x][1] = min(f[y][0] + \sum{(y!=z)f[z][3]})\)

x的儿子中有一个一定覆盖的爷爷，同时覆盖到兄弟（因为y一定是选了），其他的儿子只需要覆盖的自己的儿子即可

  • \(f[x][2] = min(f[y][1] + \sum{(y!=z)f[z][2]})\)

同理，有一个儿子覆盖到父亲，但无法覆盖到y的兄弟，所以其他儿子要覆盖到自己

  • \(f[x][3] = \sum{f[y][2]}\)

让每个儿子覆盖到自己即可

  • \(f[x][4] = \sum{f[y][3]}\)

让每个儿子覆盖到自己的儿子

注意：

f[x][i]包含f[x][i+1]，若f[x][i]比f[x][i+1]更优，f[x][i+1]应更新

代码

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
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

template<typename T> inline void read(T &x) {
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

const int N = 1005;

struct Edge {
    int nxt, to;
};

int n, cnt;
int head[N], f[N][5];
Edge e[N<<1];

inline void add(int u, int v) {
    e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
}

void dfs(int x, int fa) {
    // 记录f[y][2], f[y][3]的总和，后面容斥即可
    int sum2 = 0, sum3 = 0, y, tot;
    for (int i = head[x]; i; i = e[i].nxt)
        if (e[i].to != fa) {
            y = e[i].to;
            dfs(y, x);
            sum2 += f[y][2], sum3 += f[y][3];
            tot++;
        }
    // 没有儿子特判
    if (!tot) {
        f[x][0] = f[x][1] = f[x][2] = 1;
        return;
    }
    f[x][0] = 1, f[x][1] = f[x][2] = N;
    for (int i = head[x]; i; i = e[i].nxt)
        if (e[i].to != fa) {
            y = e[i].to;
            f[x][0] += f[y][4];
            f[x][1] = min(f[x][1], f[y][0] + sum3 - f[y][3]);
            f[x][2] = min(f[x][2], f[y][1] + sum2 - f[y][2]);
            f[x][3] += f[y][2];
            f[x][4] += f[y][3];
        }
    // 检查最小值
    for (int i = 1; i < 5; ++i)
        f[x][i] = min(f[x][i], f[x][i-1]);
}

int main() {
    read(n);
    for (int i = 2, x; i <= n; ++i)
        read(x), add(x, i), add(i, x);
    dfs(1, 0);
    printf("%d\n", f[1][2]);
}