【洛谷P1352】没有上司的舞会【树形DP】

本文主要是介绍【洛谷P1352】没有上司的舞会【树形DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P1352
给出一棵带点权的树，若选择一个点，那么不能选择这个点的父节点。求最大点权和。

---

思路：

很经典的一道树形DP题目。当然DFS也应该可以过。
设$f[i][0/1]$表示选择或不选择第$i$个结点的最大点权和。那么我们如果选择了这个点，那么它的子节点就不能选择，就有方程：
$$f[i][1]=\sum _{j=1}^{son[i]}f[j][0]$$
那如果不选这个点，那么子节点选或不选都可以，那么：
$$f[i][0]=\sum _{j=1}^{son[i]}max(f[j][1],f[j][0])$$

---

代码：

#include <cstdio>
#include <map>
using namespace std;int n,x,y,f[6001][2],num[6001],a[6001];
bool not_root[6001];
map<pair<int,int>,int> son;void dp(int x)  //递归
{f[x][0]=0;f[x][1]=a[x];  //初始化for (int i=1;i<=num[x];i++)  //枚举所有子节点{dp(son[make_pair(x,i)]);  //求子节点的最优答案f[x][0]+=max(f[son[make_pair(x,i)]][0],f[son[make_pair(x,i)]][1]);  //方程1f[x][1]+=f[son[make_pair(x,i)]][0];  //方程2}
}int main()
{scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d",&a[i]);while (scanf("%d%d",&x,&y)){if (!x&&!y) break;son[make_pair(y,++num[y])]=x;not_root[x]=true;  //有父亲就肯定不是根节点}for (int i=1;i<=n;i++)if (!not_root[i])  //是根节点{dp(i);printf("%d\n",max(f[i][0],f[i][1]));return 0;}
}

这篇关于【洛谷P1352】没有上司的舞会【树形DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---