利用树形DP解决的几道有意思的题目

记录了树形DP模型的几道有意思的问题（没有上司的舞会、战略游戏、皇宫看守）。

没有上司的舞会

问题描述

如没有上司的舞会所描述：

Ural 大学有$N$名职员，编号为 1~$N$。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数$H_i$给出，其中$1\leq i\leq N$。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式：

第一行一个整数$N$。

接下来$N$ 行，第$i$行表示$i$号职员的快乐指数$H_i$。

接下来$N-1$行，每行输入一对整数$L$，$K$，表示$K$是$L$的直接上司。（即，后一个数是前一个数的父节点）。

输出格式：

输出最大的快乐指数。

数据范围：

$$1≤N≤6000\\ −128≤H_i≤127$$

输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

5

问题分析

题目想表达的是，对于树中的某个节点，如果选择了这个节点，那么不能再选择它的父节点或者子节点，求快乐指数的最大值。即，对于树中的某一条边，最多只能选择这条边的一个节点，求节点权重的最大值。

考虑使用一个二维数组$f(i,s)$来存储选或不选该点所能获得的快乐指数的最大值，其中$i\in\{1,2,…,n\}$，表示选择的点，$s\in\{0,1\}$，表示选或不选的状态（0表示不选择该点，1表示选择该点）。自底向上递归求得树的根节点选或不选所能获得的最大值。状态方程可以表示为：

$$\begin{align} &f(i,0)=\sum_j\max(f(j,0),f(j,1))\\ &f(i,1)=\sum_jf(j,0)+happy_i \end{align}$$

其中，$j$表示$i$的子节点。

代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;
int e[N], ne[N], h[N], idx;
int happy[N];
int f[N][2];
bool has_father[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
    f[u][1] = happy[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> happy[i];
    int l, k;
    for (int i = 0; i < n - 1; i ++) {
        cin >> l >> k;
        add(k, l);
        has_father[l] = true;
    }
    // 由于题目没有确定根节点，需要手动寻找根节点
    int root = 1;
    while (has_father[root]) root ++;
    dfs(root);
    
    cout << max(f[root][0], f[root][1]) << endl;
    return 0;
} 

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

战略游戏

问题描述

如战略游戏所描述：

鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时他找不到解决问题的方法，这让他很伤心。

现在他有以下问题。

他必须保护一座中世纪城市，这条城市的道路构成了一棵树。

每个节点上的士兵可以观察到所有和这个点相连的边。

他必须在节点上放置最少数量的士兵，以便他们可以观察到所有的边。

你能帮助他吗？

输入格式：

输入包含多组测试数据，每组测试数据用以描述一棵树。

对于每组测试数据，第一行包含整数$N$，表示树的节点数目。

接下来$N$行，每行按如下方法描述一个节点。

节点编号：(子节点数目) 子节点 子节点 …

节点编号从0到$N-1$，每个节点的子节点数量均不超过10，每个边在输入数据中只出现一次。

输出格式：

对于每组测试数据，输出一个占据一行的结果，表示最少需要的士兵数。

数据范围：

$$0<N≤1500,$$

一个测试点所有$N$相加之和不超过 300650。

输入样例：

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

输出样例：

1
2

问题分析

分析题意，与没有上司的舞会一题的要求正好相反，即，对于树中的某一条边，最少选择这条边的一个节点，求节点权重的最小值。它们是对称问题。

与没有上司的舞会一题类似，考虑使用一个二维数组$f(i,s)$来存储选或不选该点所需士兵的最小值，其中$i\in\{1,2,…,n\}$，表示选择的点，$s\in\{0,1\}$，表示选或不选的状态（0表示不选择该点，1表示选择该点）。自底向上递归求得树的根节点选或不选所能获得的最小值。状态方程可以表示为：

$$\begin{align} &f(i,0)=\sum_jf(j,1)\\ &f(i,1)=\sum_j\min(f(j,0),f(j,1))+1 \end{align}$$

其中，$j$表示$i$的子节点。

代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;
int e[N], ne[N], h[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
    f[u][0] = 0, f[u][1] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][1];
        f[u][1] += min(f[j][0], f[j][1]);
    }
}

int main() {
    int n;
    while (cin >> n) {
        // 对每个测试进行初始化
        idx = 0;
        memset(h, -1, sizeof h);
        memset(has_father, 0, sizeof has_father);
        for (int i = 0; i < n; i ++) {
            int a, k, b;
            scanf("%d:(%d)", &a, &k);
            for (int j = 0; j < k; j ++) {
                scanf("%d", &b);
                add(a, b);
                has_father[b] = true;
            }
        }
        // 寻找根节点
        int root = 0;
        while (has_father[root]) root ++;
        
        dfs(root);
        cout << min(f[root][0], f[root][1]) << endl;
    }
    return 0;
}

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

皇宫看守

问题描述

如皇宫看守所描述：

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。

皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。

已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。

大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式：

输入中数据描述一棵树，描述如下：

第一行$n$，表示树中结点的数目。

第二行至第$n+1$行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号$i$，在该宫殿安置侍卫所需的经费 $k$，该结点的子结点数$m$，接下来$m$个数，分别是这个结点的$m$个子结点的标号$r_1,r_2,…,r_m$。

对于一个$n$个结点的树，结点标号在1到$n$之间，且标号不重复。

输出格式：

输出一个整数，表示最少的经费。

数据范围：

$$1≤n≤1500$$

输入样例：

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出样例：

25

样例解释：

在2、3、4结点安排护卫，可以观察到全部宫殿，所需经费最少，为 16 + 5 + 4 = 25。

问题分析

该问题乍一看好像与战略游戏一题一样，但是仔细一分析其实两题完全不一样。可以想像一下有一棵四层的树，如果将所有护卫只安排在第一层和第四层，也是符合题意的，因为护卫可以观察到四层所有的宫殿，但是不符合战略游戏一题的题意，因为第二层与第三层之间的边无法观察到，因此不能用战略游戏一题的解法来解决此问题。

同样的，我们可以考虑使用一个数组$f(i,s)$来表示点$i$在三个状态$s$时的最小花费，其中$s\in\{0,1,2\}$，$s=0$表示该点可以被父节点看到，$s=1$表示该点可以被子节点看到，$s=2$表示在该点安排护卫。用$j$和$k$表示$i$的子节点，可以得到以下状态方程：

$$\begin{align} &f(i,0)=\sum_j\min(f(j,1),f(j,2))\\ &f(i,1)=\sum_j(f(j,2)+\sum_{k\neq j}\min(f(k,1),f(k,2)))\\ &f(i,2)=\sum_j\min(f(j,0),f(j,1),f(j,2)) \end{align}$$

注意到：

$$\sum_{k\neq j}\min(f(k,1),f(k,2))=f(i,0)-\min(f(j,1),f(j,2))$$

因此可以简化方程如下：

$$\begin{align} &f(i,0)=\sum_j\min(f(j,1),f(j,2))\\ &f(i,1)=\sum_j(f(j,2)+f(i,0)-\min(f(j,1),f(j,2)))\\ &f(i,2)=\sum_j\min(f(j,0),f(j,1),f(j,2)) \end{align}$$

通过自底向上递归，最后输出根节点$r$的状态1和状态2的最小值$\min(f(r,1),f(r,2))$即可（根节点没有父节点，没有状态0）。

代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1510;
int e[N], ne[N], h[N], idx;
int w[N], f[N][3];
bool has_father[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u) {
    f[u][2] = w[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
    }
    f[u][1] = 0x3f3f3f3f;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
    }
}

int main() {
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    int id, cost, cnt;
    for (int i = 0; i < n; i ++) {
        cin >> id >> cost >> cnt;
        w[id] = cost;
        int node;
        for (int j = 0; j < cnt; j ++) {
            cin >> node;
            add(id, node);
            has_father[node] = true;
        }
    }
    int root = 1;
    while (has_father[root]) root ++;
    
    dfs(root);
    
    cout << min(f[root][1], f[root][2]) << endl;
    return 0;
}

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$