TT的苹果树【树形dp】

问题描述

在大家的三连助攻下，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

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

Sample Input

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

Sample Output

5

问题分析

苹果树很显然是树结构。暴力搜索是会超时的，我们发现子树是他的子结构，所以可以采用动态规化的方法去解决，即树形dp。

定义状态：
• 定义 f[i][0/1] 表示以 i 为节点的子树所能得到的最大的气氛值。
• f[i][0] 表示以 i 为子树且未选择 i 号节点；
• f[i][1] 表示以 i 为子树且选择了 i 号节点
• 最终答案就是 max(f[root][0], f[root][1])
• 注意，子树的求解过程能够很好地体现dp过程中最优子结构的性质。

状态转移过程

• 父节点不摘，子节点可以摘，也可以不摘。
• 父节点摘，子节点只能不摘。
• 枚举量x为当前节点i到能直接到达的所有的子节点。

#include
#include
int w[6010],head[6010],f[6010][2],d[6010],q[6010];//f[i][0]不取点i，f[i][1]取点i 
struct Edge{int to,next;
}e[6010];
int main(){int n,x,y;scanf("%d",&n);while(n!=0){for(int i=1;i<=n;i++)scanf("%d",&w[i]);memset(d,0,sizeof d);memset(f,0,sizeof f);memset(head,0,sizeof head);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);e[i].to=y,e[i].next=head[x];head[x]=i;d[y]++;}int qt=0,p=0;for(int i=1;i<=n;i++)if(d[i]==0)q[qt++]=i;while(p<n){int i=q[p++];f[i][1]+=w[i];if(f[i][0]>f[i][1])f[i][1]=f[i][0];for(int j=head[i];j;j=e[j].next){int fa=e[j].to;d[fa]--;f[fa][1]+=f[i][0];if(f[i][0]>f[i][1])f[fa][0]+=f[i][0];else f[fa][0]+=f[i][1];if(d[fa]==0)q[qt++]=fa;	}}if(f[q[n-1]][0]>f[q[n-1]][1])printf("%d\n",f[q[n-1]][0]);else printf("%d\n",f[q[n-1]][1]);scanf("%d",&n);	}return 0;
}

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