程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu1520Anniversary party 樹形dp水題

hdu1520Anniversary party 樹形dp水題

編輯:C++入門知識

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;
}















  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved