hdu1520Anniversary party 樹形dp水題
/*
dp[i][0]表示第i個人不去的時候能得到的最大值
dp[i][1]表示第i個人去的時候得到的最大值
狀態轉移方程：
dp[i][0]+=max(dp[next][0],dp[next][1])
dp[i][1]+=dp[next][0]
其中next為其子節點
*/
#include
#include
#include
#include
using namespace std;
#define maxn 6010
vector vec[maxn];
int dp[maxn][2];
int value[maxn];
void dfs(int root)
{
int i;
for(i=0;i
{
int next=vec[root][i];
dfs(next);
dp[root][0]+=max(dp[next][0],dp[next][1]);
dp[root][1]+=dp[next][0];
}
}
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
int i,j;
memset(dp,0,sizeof(dp));
for(i=1;i<=N;i++)
scanf("%d",&dp[i][1]);
int l,k;
for(i=0;i<=N;i++)
vec[i].clear();
int temp[maxn];
int root;
memset(temp,0,sizeof(temp));
while(scanf("%d%d",&l,&k),l||k)
{
vec[k].push_back(l);
temp[l]=1;
}
for(i=1;i<=N;i++)
if(!temp[i])
root=i;
dfs(root);
printf("%d\n",max(dp[root][0],dp[root][1]));
}
return 0;
}
