HDU 1520 Anniversary party 树形DP
来源：程序员人生 发布时间：2014-09-16 21:22:04 阅读次数：2365次
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520
题意：给出一个职场关系图，每个人有自己的价值，并且每个人只有一个领导，我要邀请的人不可以是一个人和他的直系领导，问最多能邀请到多少价值的人。
思路：入门题，就是把简单DP运用到了树这种数据结构里，蛮有趣的。看题意应该叫森林DP比较合适一点。首先是建树，找到的根节点就是没有父亲节点的节点。对于树上的一个节点u，dp[u][0]代表着不选择这个节点能得到的最大价值，dp[u][1]代表着选择这个节点能得到的最大价值。
状态转移方程：dp[u][0]=sum(max(dp[v][0],dp[v][1]))。不选当前节点，那么他的每个子节点都是可以选也可以不选。
dp[u][1]=sum(dp[v][0])。选择当前节点，那么他的每个子节点都不可以选择。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 6005
#define INF 0x7fffffff
typedef long long LL;
using namespace std;
int score[maxn],head[maxn],top,dp[maxn][2];
bool from[maxn];
void init()
{
memset(head,-1,sizeof(head));
memset(from,0,sizeof(from));
memset(dp,0,sizeof(dp));
top=0;
}
struct Edge
{
int v;
int next;
} edge[maxn];
int add_edge(int u,int v)
{
edge[top].v=v;
edge[top].next=head[u];
head[u]=top++;
}
void dfs(int u)
{
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].v;
dfs(v);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][1],dp[v][0]);
}
dp[u][1]+=score[u];
}
int main()
{
int tot,u,v;
while(~scanf("%d",&tot))
{
init();
for(int i=1; i<=tot; i++)
scanf("%d",&score[i]);
while(scanf("%d%d",&u,&v))
{
if(u==0&&v==0)
break;
add_edge(v,u);
from[u]=true;
}
for(int i=1; i<=tot; i++)
{
if(!from[i])
dfs(i);
}
int ans=0;
for(int i=1; i<=tot; i++)
{
if(from[i]==0)
ans+=max(dp[i][0],dp[i][1]);
}
printf("%d
",ans);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
