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题目，原题为没有上司的舞会，对于此题，首先应该通过入度确定根节点，然后进行DP。

设dp数组为f[i][j]，其中i表示以$i$为节点的子树能够达到的最大气氛值。$j$取0或1，0表示不取$i$节点，1表示取。那么最终答案就是max(f[root][1],f[root][0])

状态转移方程也非常简单，如果当前点取，那么子树必然不能取；如果当前点不取，子树可以取也可以不取。所以状态转移方程如下所示，其中$x$是$i$的子树
f [ i ] [ 0 ] = ∑ m a x { f [ x ] [ 1 ] , f [ x ] [ 0 ] } f[i][0]=\sum max\{f[x][1],f[x][0]\} f[i][0]=∑max{f[x][1],f[x][0]}
f [ i ] [ 1 ] = a i + ∑ f [ i ] [ 0 ] f[i][1]=a_i+\sum f[i][0] f[i][1]=ai​+∑f[i][0]

完整代码

//#pragma GCC optimize(2)
//#pragma G++ optimize(2)
//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;const int maxn=6000+10;
struct node{int x,to,next;
};
node edge[maxn*2];
int n,w[maxn],head[maxn],a[maxn],l,k,cnt,_root,f[maxn][2];
void add(int x,int y){cnt++;edge[cnt].to=y;edge[cnt].next=head[x];head[x]=cnt;
}
void dp(int x){for (int i=head[x]; i; i=edge[i].next){dp(edge[i].to);f[x][0]+=max(f[edge[i].to][0],f[edge[i].to][1]);f[x][1]+=f[edge[i].to][0];}f[x][1]+=w[x];
}
int getint(){int x=0,s=1; char ch=' ';while(ch<'0' || ch>'9'){ ch=getchar(); if(ch=='-') s=-1;}while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar();}return x*s;
}
int main(){//ios::sync_with_stdio(false);//cin.tie(0);cin>>n;for (int i=1; i<=n; i++)cin>>w[i];while(cin>>l>>k && !(l==0 && k==0)){add(k,l); a[l]++;}for (int i=1; i<=n; i++){if(a[i]==0){_root=i; break;}}dp(_root);cout<<max(f[_root][0],f[_root][1])<<endl;return 0;
}

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