D - TT 的苹果树

题意:

在大家的三连助攻下，TT 一举获得了超级多的猫咪，因此决定开一间猫咖，将快乐与大家一同分享。并且在开业的那一天，为了纪念这个日子，TT 在猫咖门口种了一棵苹果树。

一年后，苹果熟了，到了该摘苹果的日子了。

已知树上共有 N 个节点，每个节点对应一个快乐值为 w[i] 的苹果，为了可持续发展，TT 要求摘了某个苹果后，不能摘它父节点处的苹果。

TT 想要令快乐值总和尽可能地大，你们能帮帮他吗？

Input
结点按 1～N 编号。

第一行为 N (1 ≤ N ≤ 6000) ，代表结点个数。

接下来 N 行分别代表每个结点上苹果的快乐值 w[i]（-128 ≤ w[i] ≤ 127)。

接下来 N-1 行，每行两个数 L K，代表 K 是 L 的一个父节点。

输入有多组，以 0 0 结束。

Output
每组数据输出一个整数，代表所选苹果快乐值总和的最大值。

输入样例

7
1
1
1
1
1
1
1
1 3
7 4
2 3
4 5
6 4
3 5
0 0

输出样例

5

思路:

很明显是树结构，采用前向星存储；
选择了一个子树的根则不能选择他的儿子或者选择其儿子不选择根；
定义状态f[i][0/1]表示以 i 为节点的子树所能得到的最大的快乐值
f[i][0]表示以i为子树且未选择i号节点
f[i][1]表示以i为子树且选择了i号节点
最终答案即max(f[root][0],f[root][1])
状态转移方程：

f[i][0]=∑max(f[x][1],f[x][0])
f[i][1]=ai+∑f[x][0] x表示i可直接到达的子节点

使用DFS从根节点出发搜索整个树，完成自下而上的状态转移

代码:

#include 
#include 
#include 
using namespace std;
const int maxn=6000+5;
int n,u,v;
int head[maxn],to[maxn],nxt[maxn],tot=0,indgree[maxn];
int dp[maxn][2];void add(int &u,int &v)
{tot++;to[tot]=v;nxt[tot]=head[u];head[u]=tot;
}
void dfs(int root)
{for(int i=head[root]; i!=0; i=nxt[i]){dfs(to[i]);dp[root][0]+=max(dp[to[i]][0],dp[to[i]][1]);dp[root][1]+=dp[to[i]][0];}
}int main()
{scanf("%d",&n);memset(indgree,0,sizeof(indgree));for(int i=1; i<=n; i++)	scanf("%d",&dp[i][1]);while(scanf("%d %d",&u,&v)&&(u!=0&&v!=0)){add(v,u);indgree[u]++;}int root;for(int i=1; i<=n; i++){if(indgree[i]==0){root=i;break;}}dfs(root);printf("%d",max(dp[root][0],dp[root][1]));return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！