Week13—苹果树

问题描述

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

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

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

TT 想要令快乐值总和尽可能地大，你们能帮帮他吗？
【输入】
结点按 1～N 编号。

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

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

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

输入有多组，以 0 0 结束。
【输出】
每组数据输出一个整数，代表所选苹果快乐值总和的最大值。
【输入样例】

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

【输出样例】

5

问题分析

首先存储苹果树结构，选择链式前向星，本题与上司跳舞完全相同，我们将每个节点分成两种情况，dp[1][node]是选了当前子树根节点的最大值,dp[0][node]是没选当前子树根节点的最大值
如果选择dp[1][node],那么这个节点的孩子就不可以被选择，dp[1][node]=Σdp[0][kid]，如果不选择node节点，那么任意一个孩子节点都可以被选择，每个孩子节点选那个最大的,把所有孩子结点的累加起来,并且加上本来根节点的权重
状态转移方程为：
dp[1][p]+=dp[0][kid];
dp[0][p]+=max(dp[0][kid],dp[1][kid]);

代码

#include
#include
#include
using namespace std;
const int nmax=6e3+10;
int head[nmax],tot=1;
int w[nmax],p[nmax],dp[2][nmax];//dp[1][]选中,dp[0][]没有struct edge
{int to,parent,next;
}edges[nmax];void add(int parent,int kid)
{p[kid]=parent;//父节点 edges[++tot].to=kid;edges[tot].parent=parent;edges[tot].next=head[parent];head[parent]=tot;
}
void solve(int p)
{for(int i=head[p];i;i=edges[i].next){int kid=edges[i].to;solve(kid);dp[1][p]+=dp[0][kid];dp[0][p]+=max(dp[0][kid],dp[1][kid]);}dp[1][p]+=w[p];
}
int main(){int N,L,K;while(cin>>N){if(N==0) break;memset(head,0,sizeof(head));memset(dp,0,sizeof(dp));memset(p,0,sizeof(p));tot=1;for(int i=1;i<=N;i++)cin>>w[i];for(int i=1;i<N;i++){cin>>L>>K;add(K,L);}//找到根int root=1;while(p[root])root=p[root];solve(root);int ans=max(dp[0][root],dp[1][root]);cout<<ans<<endl;}return 0;
}

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