本文主要是介绍hdu 1520 Anniversary party(基本树形DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、http://acm.hdu.edu.cn/showproblem.php?pid=1520
2、题目大意：
有n个员工，每个员工都有一个rating值，给出员工之间的上下级的关系，要求是有直接上下级关系的员工不能同时出席，现在要求的是选择哪些员工出席，会使得他们的rating之和最大
定义dp[i][1]表示i员工出席时的最大值，dp[i][0]表示i员工不出席时的最大值
dp[i][1]=dp[v][0]//当i员工出席时，就等于他的所有直接下属v不出席时的最大值
dp[i][0]=max(dp[v][1],dp[v][0])//当i员工不出席时，就等于他的下属出席或者不出席的最大值
3、题目：
Anniversary party
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3617 Accepted Submission(s): 1680
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
5
4、AC代码：
#include<stdio.h>
#include<vector>
using namespace std;
#define N 6005
vector<int> vec[N];
int rating[N];
int f[N];
int dp[N][2];//dp[i][1]表示i结点选择，dp[i][0]表示i结点不选择
void dfs(int root)
{dp[root][1]=rating[root];for(int i=0; i<vec[root].size(); i++){int v=vec[root][i];dfs(v);dp[root][1]+=dp[v][0];dp[root][0]+=max(dp[v][1],dp[v][0]);}
}
int main()
{int n,l,k;while(scanf("%d",&n)!=EOF){for(int i=1; i<=n; i++){scanf("%d",&rating[i]);f[i]=-1;//标记根节点vec[i].clear();dp[i][0]=0;dp[i][1]=0;}while(scanf("%d%d",&l,&k)!=EOF){if(l==0 && k==0)break;vec[k].push_back(l);f[l]=k;}int a=1;while(f[a]!=-1){a=f[a];}dfs(a);printf("%d\n",max(dp[a][1],dp[a][0]));}return 0;
}
这篇关于hdu 1520 Anniversary party(基本树形DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
