我是靠谱客的博主 无聊奇异果,这篇文章主要介绍浅谈树形DP,现在分享给大家,希望可以做个参考。

在动态规划问题中,我们时常能遇到类似于树上的动态规划问题,对于这种问题,普通的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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(47)

评论列表共有 0 条评论

立即
投稿
返回
顶部