一.算法思想

　　树形dp就是在树上做dp

　　通常，我们采用dfs的方式遍历一个树

　　而这与dp的记忆化搜索写法不谋而合

　　所以我们多采用记忆化搜索的思想

 1 void dfs(int u) //u为当前节点 fa为父亲节点
 2 {
 3     //这里写一些边界条件 如if(l == r)之类
 4 
 5     if (f[u]) return f[u]; //算法的核心 充分利用已有结果
 6 
 7     //循环枚举
 8     e.g.
 9     for (auto v : e[u]) {
10         if (v == fa) continue; 
11         f[v] = f[u] ..... //转移
12         dfs(v, u) .....  //递归
13     }
14 
15     //可能要return
16 }

 

二.经典例题

第一阶段：形式上的小变化

  • 你能认出它树的结构，但具体的写法上略有不同

1.Luogu 1352 没有上司的舞会

　　对于一个子节点v而言，它的父节点是u

　　令f[i][0]代表i点不选的最大得分

　　　　f[i][1]代表i点选的最大得分

　　则f[u][0] += max(f[v][0], f[v][1])

　　　　f[u][1] += f[v][0]

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define rep(i, a, b) for (int i = a; i <= b; ++i)
 4 const int N = 6007;
 5 
 6 int n, a[N], f[N][2]; vector <int> e[N];
 7  
 8 inline void dfs(int u, int fa) {
 9     f[u][1] = a[u];
10     for (auto v : e[u]) { if (v == fa) continue;
11         dfs(v, u);
12         f[u][0] += max(f[v][0], f[v][1]);
13         f[u][1] += f[v][0];
14     }
15 }
16 
17 int main() {
18     scanf("%d", &n);
19     rep(i ,1, n) {
20         scanf("%d", &a[i]);
21     } int root = n * (n + 1) / 2;
22     rep(i, 1, n) { int x, y;
23         scanf("%d%d", &x, &y);
24         e[y].push_back(x); root -= x;
25     }
26     dfs(root, 0);
27     printf("%d\n", max(f[root][0], f[root][1]));
28     return 0;
29 }

View Code

 

 

 

2.Luogu 1040 加分二叉树

　　令人头疼的是如何循环枚举这个问题

　　而产生这个问题的原因就是我不知道这颗树的形状

　　但是我们知道它的中序遍历是1到n

　　所以我们考虑每次dfs一个区间[L, R]

　　枚举根节点k

　　将问题分成两个子问题[L, k – 1]和[k + 1, R]即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define rep(i, a, b) for (int i = a; i <= b; ++i)
 4 const int N = 37;
 5 
 6 int n, f[N][N], fa[N][N];
 7 
 8 inline int dfs(int L, int R) { 
 9     if (L > R) return 1;
10     if (f[L][R]) return f[L][R];
11     rep(i, L, R) { int k = dfs(L, i - 1) * dfs(i + 1, R) + f[i][i];
12         if (k > f[L][R]) {
13             f[L][R] = k; fa[L][R] = i;
14         }
15     }
16     return f[L][R];
17 }
18 
19 void print(int L, int R) { 
20     if (L > R) return;
21     printf("%d ", fa[L][R]); print(L, fa[L][R] - 1); print(fa[L][R] + 1, R);
22 } 
23 
24 int main() {
25     scanf("%d", &n);
26     rep(i, 1, n) {
27         scanf("%d", &f[i][i]); 
28         fa[i][i] = i;
29     }
30     printf("%d\n", dfs(1, n)); print(1, n);
31     return 0;
32 }

View Code

 

3.Luogu 1270 “访问”美术馆

　　根据题意我们发现美术馆就是一颗树的结构

　　对于这样古怪的输入我们在dfs的同时输入，以dfs序作为点的编号即可

　　有趣的是，本题的条件还有时间这一项

　　所以对于当前一个状态，我们的量有几号点，时间

　　而需要求的值是最大偷画数

　　所以我们设计方程f[i][j] 代表到i号点，第j时间的最大偷画数

　　而对此，我们分类：

　　1.如果当前是岔路口，令接下来的两点编号为L和R，时间为t 则t可能从L转移i时间再从R转移t-i时间而达成

　　　　对于道路需要往返这个问题，我们考虑再i时间内已包含了走过道路两遍的时间，这样这个问题就解决了

　　2.如果是藏画地，则我们在时间允许的情况内尽可能多的去画

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define rep(i, a, b) for(int i = a; i <= b; ++i)
 5 
 6 const int N = 107;
 7 const int S = 607;
 8 
 9 int s, n, f[N][S]; 
10 
11 void dfs(int u) {
12     int time, paint;
13     scanf("%d%d", &time, &paint);
14     if (!paint) {
15         int L = ++n, r = ++n;
16         dfs(L), dfs(r);
17         rep(i, time * 2 + 1, s - 1) rep(j, 0, i - time * 2) { //往返时间
18             f[u][i] = max(f[u][i], f[L][j] + f[r][i - j - time * 2]);
19         }
20     }
21     else {
22         rep(i, time * 2 + 1, s - 1) { //还是边界
23             f[u][i] = min((i - time * 2) / 5, paint); //最多取画
24         } 
25     }
26 }
27 
28 int main() {
29     scanf("%d", &s);
30     
31     dfs(0);
32     
33     printf("%d\n", f[0][s - 1]); //注意读题 警察在s秒抓到他，所以他必须最迟在s - 1秒中时结束
34     
35     return 0;
36 }

View Code

第二阶段：操作上的小变化

版权声明：本文为Fo0o0ol原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Fo0o0ol/p/11318749.html