【Week 13 作业D】TT的苹果树

题目描述

在大家的三连助攻下，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[n]/[0]为不取节点n时，以节点n为根的子树可取到的最大值；dp[n]/[1]为取节点n时，以节点n为根的子树可取到的最大值；
状态转移方程dp[f]/[0]为所有max(dp[c]/[0]，dp[c]/[1])的和，其中c为f的孩子节点。
dp[f]/[1]为所有dp[c]/[0]的和，其中c为f的孩子节点。
最终结果即为max(dp[root]/[0],dp[root]/[1]),root为整棵树的根。也可不求根节点，直接取dp数组中的最大值。

代码

#include 
#include 
#include
#include  
using namespace std;
const int size=6000+10;
int w[size];
int dp[size][2];
bool vis[size];
vector<int> e[size];
int N;
void sdfs(int ,int);
void dfs(int x)
{if(!vis[x]){sdfs(x,0);sdfs(x,1);}
}
void sdfs(int f,int flag)
{vis[f]=true;if(flag==0){for(vector<int>::iterator it=e[f].begin();it!=e[f].end();it++){dfs(*it);dp[f][0]+=max(dp[*it][0],dp[*it][1]);}}else{for(vector<int>::iterator it=e[f].begin();it!=e[f].end();it++){dfs(*it);dp[f][1]+=dp[*it][0];}dp[f][1]+=w[f];}
}
void solve()
{int ans=0;memset(dp,0,sizeof(dp));for(int i=1;i<=N;i++){if(!vis[i])dfs(i);int temp=max(dp[i][0],dp[i][1]);ans=max(ans,temp);}printf("%d\n",ans);
}
int main(int argc, char** argv) {while(scanf("%d",&N)&&N!=0){memset(vis,false,sizeof(vis));for(int i=1;i<=N;i++)scanf("%d",&w[i]);for(int i=1;i<N;i++){int a,b;scanf("%d%d",&a,&b);e[b].push_back(a);}solve();}return 0;
}

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