题目描述
选了某个节点就不能选父节点和子节点。求最大权值和。
样例
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
5
算法1
(树形DP) $O(n)$
题解里的人都建图了啊,但是这题明明可以不用这么麻烦的……
本题稍加思索即可得出为树形dp。
每个人只有两种状态,则设$dp[0][i]$为第$i$个人不来,他的下属所能获得的最大快乐值;$dp[1][i]$为第$i$个人来,他的下属所能获得的最大快乐值。
所以容易推出状态转移方程:
$dp[0][i]=\sum\limits_{u=sons}max(dp[1][u],dp[0][u])$当前节点不选,那么子节点随意
$dp[1][i]=\sum\limits_{u=sons}dp[0][u]+happy[i]$当前节点选,子节点不能选
分析可得,每个人的状态要在下属的状态更新完了才能更新,所以用类似拓扑的方法,只记录每个子节点的父亲,最后从所有入度为$0$的点开始跑就行了。在更新每个子节点时顺便让父节点加上自己的权值,最后访问父节点时权值已经更新好了,就可以省去建图的麻烦。
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
int dp[2][6010];//dp解释见上
int f[2][6010];//f[0]为父亲,f[1]为高兴值
int ind[6010];//入度
int vis[6010];//访问标记
int root;//树的根
void dfs(int u){//递归从后往前更新
if(!u) return;
vis[u]=1;//已访问
root=u;//最后一个访问到的一定是根,所以一直更新根就行了
dp[0][f[0][u]]+=max(dp[1][u]+f[1][u],dp[0][u]);//给父亲更新
dp[1][f[0][u]]+=dp[0][u];
ind[f[0][u]]--;//更新完一个子节点
if(!ind[f[0][u]]) dfs(f[0][u]);//在所有子节点更新后再更新(入度为0)
}
int main(){
int n=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&f[1][i]);
int a,b;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
f[0][a]=b;//保存节点信息
ind[b]++;
}
for(int i=1;i<=n;i++)
if(!vis[i]&&!ind[i])//没有被访问过,没有入度,说明是叶子节点
dfs(i);
printf("%d\n",max(dp[0][root],dp[1][root]+f[1][root]));//取根节点两种方案的最大值
return 0;
}
按照老哥的思想用拓扑排序的方法做了一遍 tql tql
for (int i = 1; i <= size; ++i) 这层循环没有必要
可以直接输出 dp[0][0]吧……
如果数据在开大一点比如10^6,且形成一条链,这样的dfs会爆内存吗?
这个算不算记忆化搜索呢
本题稍加思索即可得出为树形dp。干的漂亮
《稍加思索》
入度不对吧,是出度
应该是在反图上考虑吧,父节点相应的都是入度。
毕竟入度为零的才叫做源点。
%%%
%%%
Nice!
%%%
%%%
topSort的思路很巧妙!%%
%%%
%%%
%%%
%%%
%%%