hdu1520 Anniversary party 트리 dp

1338 단어
hdu1520
이전보다 나무 가방이 훨씬 간단해졌어요. 가방의 부피 제한이 없어요.
dp[i][0] i를 뿌리로 하는 나무에서 얻은 최대 값
dp[i][1] i를 뿌리로 하는 나무에서 얻은 최대 값
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int N,V[6100];
vector<int>son[6010];
int dp[6100][2],vis[6100];

void dfs(int n){
	vis[n]=1;
	int len=son[n].size();
	dp[n][1]=V[n];
	for(int i=0;i<len;i++){
		int	k=son[n][i];
		if(vis[k])	continue;
		dfs(k);
		if(dp[n][1]<dp[n][1]+dp[k][0])	dp[n][1]=dp[n][1]+dp[k][0];
		dp[n][0]=max(dp[n][0],max(dp[n][0]+dp[k][1],dp[n][0]+dp[k][0]));
	}
}


int main()
{
	int i,j,k,u,v;
	
	while(scanf("%d",&N)!=EOF)
	{
		memset(vis,0,sizeof(vis));
		memset(dp,0,sizeof(dp));
		for(i=1;i<=N;i++){
			scanf("%d",&V[i]);
			son[i].clear();
		}
		while(scanf("%d%d",&u,&v),u||v){
			son[v].push_back(u);
			vis[u]=1;		//     
		}
		
		
		for(i=1;i<=N;i++)
			if(vis[i]==0){
				memset(vis,0,sizeof(vis));
			//	printf("%d
",i); dfs(i);//for(j=1;j<=N;j++) printf("%d %d %d
",j,dp[j][0],dp[j][1]); // printf("%d %d
",dp[i][0],dp[i][1]); printf("%d
",max(dp[i][0],dp[i][1])); } } return 0; } /* 7 1 -1 -1 -1 -1 -1 -1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 */

좋은 웹페이지 즐겨찾기