로곡P1352 상사 없는 무도회(진급 안내서, 나무형dp)

12728 단어 알고리즘 경연 진급 안내동적 기획낙곡
알고리즘 경쟁 진급 지침, 289페이지, 트리 DP 본제 요점: 1. 상태 표시: dp[x][0]는 x를 뿌리 노드로 하는 하위 나무, x가 참가하지 않고 얻은 최대 해피 값, dp[x][1]은 x가 참가하는 상황 2. 상태 이동 방정식: a)x노드가 참가하지 않고 dp[x][0]=구화max(dp[y][0], dp[y][1])(x의 모든 아이 y)b)x노드가 참가한다.그러면 x의 모든 부하 y(즉 자식)는 dp[x][1]=h[x]+구화 dp[y][0]
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 10010;
int n, root;
vector<int> son[N];
int dp[N][2], v[N], h[N];
// dp[x][0]  x       ，x   ，      happy  ， dp[x][1]    x     
// v[x]     x       

void dfs(int r)
{
	if(son[r].empty())
	{
		dp[r][0] = 0;
		dp[r][1] = h[r];
		return;
	}
	int size = son[r].size(), s1 = 0, s2 = 0;
	for(int i = 0; i < size; ++i)
	{
		int child = son[r][i];
		dfs(child);
		s1 += max(dp[child][0], dp[child][1]);
		s2 += dp[child][0];
	}
	dp[r][0] = s1;
	dp[r][1] = h[r] + s2; 
}

void solve()
{
	//      root
	for(int i = 1; i <= n; ++i)
	{
		if(!v[i])
		{
			root = i;
			break;
		}
	}
	dfs(root);
	printf("%d
", max(dp[root][0], dp[root][1]));
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", &h[i]);
	}
	int c, p;
	for(int i = 1; i < n; ++i)	// n - 1   
	{
		scanf("%d%d", &c, &p);
		v[c] = 1;
		son[p].push_back(c);
	}
	solve();
	return 0;
}

/*
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
*/

/*
5
*/
mazon CloudSearch에서 상품 검색 - No.1 데이터 투입
AWS에 대한 우선 사용자 보안 대책

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage