HDU 1520 Anniversary party 樹(shù)形DP
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-09-16 21:22:04 閱讀次數(shù)：2513次
鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1520
題意：給出一個(gè)職場(chǎng)關(guān)系圖，每個(gè)人有自己的價(jià)值，并且每個(gè)人只有一個(gè)領(lǐng)導(dǎo)，我要邀請(qǐng)的人不可以是一個(gè)人和他的直系領(lǐng)導(dǎo)，問(wèn)最多能邀請(qǐng)到多少價(jià)值的人。
思路：入門(mén)題，就是把簡(jiǎn)單DP運(yùn)用到了樹(shù)這種數(shù)據(jù)結(jié)構(gòu)里，蠻有趣的。看題意應(yīng)該叫森林DP比較合適一點(diǎn)。首先是建樹(shù)，找到的根節(jié)點(diǎn)就是沒(méi)有父親節(jié)點(diǎn)的節(jié)點(diǎn)。對(duì)于樹(shù)上的一個(gè)節(jié)點(diǎn)u，dp[u][0]代表著不選擇這個(gè)節(jié)點(diǎn)能得到的最大價(jià)值，dp[u][1]代表著選擇這個(gè)節(jié)點(diǎn)能得到的最大價(jià)值。
狀態(tài)轉(zhuǎn)移方程：dp[u][0]=sum(max(dp[v][0],dp[v][1]))。不選當(dāng)前節(jié)點(diǎn)，那么他的每個(gè)子節(jié)點(diǎn)都是可以選也可以不選。
dp[u][1]=sum(dp[v][0])。選擇當(dāng)前節(jié)點(diǎn)，那么他的每個(gè)子節(jié)點(diǎn)都不可以選擇。
代碼：
#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;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
