在动态规划问题中,我们时常能遇到类似于树上的动态规划问题,对于这种问题,普通的DP已经无法解决,只能通过遍历树形结构来进行动态规划
先来一道入门树形DP题
没有上司的舞会
题意很简单,就是1号点是CEO,即树的根,那么我们现在应该考虑的是以i这个点为根的子树的最优解是什么样子的,只有得到了以i为根的子树的最优解,我们才能再推出i的根的最优解,以此推到整棵树的根
对于这个题,我们考虑第i个人他来还是不来,因为他来与不来影响他的直接下属来不来,对于其他的间接下属,第i个人来不来是没有影响的,那么我们就可以得到转移方程,假如第i个人不来,那么第j个人可能来也可能不来,其中第i个人是第j个人的直接上司,dp[i][0]+=max(dp[j][0],dp[j][1]),假如第i个来,那么第j个人肯定不会来,所以转移方程就是dp[i][1]+=dp[j][0],最终的答案呢,就是整棵树的根来与不来的最大值,即max(dp[1][0],dp[1][1]),总结一下就是一类树形DP的特点是要先递归到叶子节点,然后从叶子节点沿着路径一路DP到整棵树的根
注意,在建树的时候可以建成单向的,也可以建成双向的,只不过双向的需要标记一下父亲,不要再递归会父亲导致死循环,单向的就不需要这样了
AC代码:
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<int>> G(n + 1); vector<int> a(n + 1); for (int i = 2; i <= n; i++) { int u; cin >> u; G[u].push_back(i); G[i].push_back(u); } for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<vector<LL>> dp(n + 1, vector<LL> (2)); function<void(int, int)> dfs = [&](int u, int fa) { dp[u][0] = 0, dp[u][1] = a[u]; for (auto v : G[u]) { if (v != fa) { dfs(v, u); dp[u][0] += max(dp[v][0], dp[v][1]); dp[u][1] += dp[v][0]; } } }; dfs(1, 0); cout << max(dp[1][1], dp[1][0]) << 'n'; return 0; }
有了以上的树形DP的入门,我们再来看一道加条件版本的树形DP
没有上司的舞会2
这道题沿用了上题思路,只不过这道题多了一个条件,即舞会的场地最多容纳m个人,虽然多了一个限制条件,但是本质还是没有改变的,我们只需要枚举容积大小,以及在子树中来了多少个人即可,然后最后假如这个人来了,需要将每种空间容积状态下的快乐值加上,这里m必须倒序枚举,如果正序,会出现类似 f[i][0][1] 先更新 f[i][1][1],f[i][1][1] 再更新 f[i][2][1],i 号员工参加了超过一次的情况。
AC代码:
#include <bits/stdc++.h> using namespace std; using LL = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> G(n + 1); vector<int> a(n + 1); for (int i = 2; i <= n; i++) { int u; cin >> u; G[u].push_back(i); } for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<vector<vector<LL>>> dp(n + 1, vector<vector<LL>> (m + 1, vector<LL> (2))); function<void(int)> dfs = [&](int u) { for (auto v : G[u]) { dfs(v); for (int k = m; k >= 0; k--) { for (int l = 0; l <= k; l++) { dp[u][k][0] = max(dp[u][k][0], dp[u][k - l][0] + max(dp[v][l][0], dp[v][l][1])); dp[u][k][1] = max(dp[u][k][1], dp[u][k - l][1] + dp[v][l][0]); } } } for (int k = m; k > 0; k--) { dp[u][k][1] = dp[u][k - 1][1] + a[u]; } dp[u][0][1] = 0; }; dfs(1); cout << max(dp[1][m][0], dp[1][m][1]) << 'n'; return 0; }
最后
以上就是无聊奇异果最近收集整理的关于浅谈树形DP的全部内容,更多相关浅谈树形DP内容请搜索靠谱客的其他文章。
发表评论 取消回复