一、树形动态规划
基于树这个数据结构的一类动态规划问题。那么如何判断一个题目是否属于树形动态规划类型，即判断数据结构是否为树以及是否符合动态规划的条件。
树形动态规划的特殊性：无环、\(DFS\) 不会重复，具有明显且严格的层级关系。
二、例题
1.[Daimayuan Online Judge.统计人数]
题目描述
一家公司里有 \(n\) 个员工，他们的编号分别是 \(1\) 到 \(n\)，其中 \(1\) 号员工是公司 \(CEO\)，\(CEO\) 在公司里没有上司。除了 \(CEO\) 外，每个人都有一个直接上司。我们想知道，每个人的团队（包括他/她自己、他/她的直接下属和间接下属）一共有多少人？
输入格式
第一行一个整数 \(n\)。接下来一行 \(n−1\) 个整数 \(f_2,f_3,…,f_n\)，其中 \(f_i\) (\(1≤f_i<i\)) 表示 \(i\) 号员工的上司的编号。
输出格式
输出一行 \(n\) 个整数，分别表示 \(1∼n\) 号员工的团队人数。
数据范围
对于所有数据，保证 \(2≤n≤10^5\)。
输入样例
5
1 2 3 1
输出样例
5 3 2 1 1
解题思路
- 方法 \(1\)：考虑 \(i\) 号员工的团队人数等于其每个直接下级的团队人数的总和 \(+1\)。
- 方法 \(2\)：从 \(CEO\) 做一遍 \(BFS\)，在 \(BFS\) 序中某个员工一定在其直接下级的前面，按照该序列的倒序依次计算每个员工的团队人数。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int e[N], ne[N], h[N], idx;
int f[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void solve(int u) {
f[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
solve(e[i]);
f[u] += f[e[i]];
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
int j;
scanf("%d", &j);
add(j, i);
}
solve(1);
for (int i = 1; i <= n; i++)
printf("%d ", f[i]);
return 0;
}
2.[Daimayuan Online Judge.没有上司的舞会]
题目描述
一家公司里有 \(n\) 个员工，他们的编号分别是 \(1\) 到 \(n\)，其中 \(1\) 号员工是公司 \(CEO\)，\(CEO\) 在公司里没有上司。除了 \(CEO\) 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。\(i\) 号员工来参加舞会会为大家带来 \(a_i\) 点快乐值。现在我们想要确定一组员工参加舞会的方案，使得快乐值总和最大。请求出快乐值总和最大是多少。
输入格式
第一行一个整数 \(n\)。接下来一行 \(n−1\) 个整数 \(f_2,f_3,…,f_n\)，其中 \(f_i\) (\(1≤f_i<i\)) 表示 \(i\) 号员工的上司的编号。
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\) 表示每个员工参加舞会带来的快乐值。
输出格式
一行一个整数表示答案。
数据范围
对于所有数据，保证 \(2≤n≤10^5,1≤a_i≤10^5\)。
输入样例
5
1 2 3 1
1 8 10 8 2
输出样例
18
解题思路
考虑 \(i\) 号员工，其有参加舞会和不参加舞会两种情况，计算两种情况对应的最大快乐值计算出来。
- 如果 \(i\) 参加舞会，则直接下级都不会参加舞会。
- 如果 \(i\) 不参加舞会，则直接下级可以参加舞会也可以不参加舞会。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, v[N];
int e[N], ne[N], h[N], idx;
LL f[N][2]; // f[i][0]表示i不参加，f[i][1]表示i参加
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void solve(int u) {
f[u][1] = v[u];
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
solve(j);
f[u][0] += max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
int j;
scanf("%d", &j);
add(j, i);
}
for (int i = 1; i <= n; i++)
scanf("%d", &v[i]);
solve(1);
printf("%lld\n", max(f[1][0], f[1][1]));
return 0;
}
3.[Daimayuan Online Judge.新的背包]
题目描述
有 \(n\) 种物品要放到一个袋子里，袋子的总容量为 \(m\)，每种物品都有 \(m\) 个，单个物品的体积都是 \(1\)。对于第 \(i\) 种物品，如果我们一共取了 \(j\) (\(j≥1\)) 个，会获得 \(w_{i,j}\) 的收益。请问如何选择物品，使得在物品的总体积不超过 \(m\) 的情况下，获得的总收益最大？请求出最大总收益。
输入格式
第一行两个整数 \(n,m\)。
接下来 \(n\) 行，每行 \(m\) 个整数 \(w_{i,1},…,w_{i,m}\)。
输出格式
一行一个整数表示答案。
数据范围
对于所有数据，保证 \(1≤n,m≤500,1≤w_{i,j}≤1000\)。
输入样例
5 5
5 1 1 5 2
2 7 8 2 4
4 1 6 9 1
8 10 10 6 1
8 7 2 8 10
输出样例
28
解题思路
状态表示：\(f[i][j]\) 表示考虑前 \(i\) 种物品，总体积不超过 \(j\) 的最大收益。
状态计算：\(f[i][j]=max_{0≤k≤j}(f[i-1][j-k]+w[i][k])\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 510;
int n, m;
int w[N][N];
int f[N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &w[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++)
for (int k = 0; k <= j; k++)
f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
printf("%d\n", f[n][m]);
return 0;
}
4.[Daimayuan Online Judge.没有上司的舞会2]
题目描述
一家公司里有 \(n\) 个员工，他们的编号分别是 \(1\) 到 \(n\)，其中 \(1\) 号员工是公司 \(CEO\)，\(CEO\) 在公司里没有上司。除了 \(CEO\) 外，每个人都有一个直接上司。今天公司要办一个舞会，为了大家玩得尽兴，如果某个员工的直接上司来了，他/她就不想来了。\(i\) 号员工来参加舞会会为大家带来 \(a_i\) 点快乐值。由于场地有大小限制，场地最多只能容纳 \(m\) 个人。现在我们想要确定一组员工参加舞会的方案，使得快乐值总和最大。请求出快乐值总和最大是多少。
输入格式
第一行两个整数 \(n,m\)。
接下来一行 \(n−1\) 个整数 \(f_2,f_3,…,f_n\)，其中 \(f_i\) (\(1≤f_i<i\)) 表示 \(i\) 号员工的上司的编号。
接下来一行 \(n\) 个整数 \(a_1,a_2,…,a_n\) 表示每个员工参加舞会带来的快乐值。
输出格式
一行一个整数表示答案。
数据范围
对于所有数据，保证 \(2≤n≤500,0≤m≤n,1≤a_i≤100000\)。
输入样例
5 2
1 2 3 1
1 8 10 8 2
输出样例
16
解题思路
考虑 \(i\) 号员工的团队，除了考虑其自身是否参加舞会，还要考虑团队中一共有多少个人参加了。
状态表示：\(f[i][j][0]\) 和 \(f[i][j][1]\) 分别表示考虑 \(i\) 号员工团队，团队中最多 \(j\) 人参加，其不参加/参加的快乐值
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
typedef long long LL;
int n, m, v[N];
int e[N], ne[N], h[N], idx;
LL f[N][N][2]; // f[i][j][0]表示包括i及其下属且最多参加j人且i不参加
// f[i][j][1]表示包括i及其下属且最多参加j人且i参加
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void solve(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
solve(e[i]);
for (int j = m; j >= 0; j--)
for (int k = 0; k <= j; k++) {
f[u][j][0] = max(f[u][j][0], f[u][j - k][0] + max(f[e[i]][k][0], f[e[i]][k][1]));
f[u][j][1] = max(f[u][j][1], f[u][j - k][1] + f[e[i]][k][0]);
}
}
for (int j = m; j; j--)
f[u][j][1] = f[u][j - 1][1] + v[u];
f[u][0][1] = 0;
}
int main() {
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
int j;
scanf("%d", &j);
add(j, i);
}
for (int i = 1; i <= n; i++)
scanf("%d", &v[i]);
solve(1);
printf("%lld\n", max(f[1][m][0], f[1][m][1]));
return 0;
}