[POJ] 2342 Anniversary party

題目網址: http://poj.org/problem?id=2342

題意: 有間公司有N個員工(1...N)，現在要開始一個party，由於每個人都不想與自己的直接上司共同在場，且每個人都有一個歡樂值，如果直接上司不在場，則此人擁有其歡樂值，現在給定N-1個員工關係L K，分別代表員工K為員工L的直接上司，問你要邀請哪些人才能擁有全場最大歡樂值，最後輸出最大歡樂值。



解法: 整個公司的所有員工(包含老闆-root)，會形成一個樹狀結構，以dp[i][j]代表以員工i為樹根的子樹j情況(j == 0, 員工i不在場; j == 1, 員工i在場)時的最大歡樂值，而狀態轉移方程:

dp[i][j] = { tree[i].val+{ dp[k][0], for k是i的直接下屬 }, if j == 1
           { { max( dp[k][0], dp[k][1] ), for k是i的直接下屬 }, if j == 0

*tree[i].val 表示員工i的歡樂值

當員工i在場時，最大歡樂值為所有i的直接下屬不在場歡樂值的和再加上員工i的歡樂值；若員工i不在場，最大歡樂值為所有i的直接下屬在場或不在場(取最大)的和。
再以DFS考慮"老闆"在場或不在場的情況，答案為 max( dp[老闆][0], dp[老闆][1] )。

TAG: TreeDP, DFS, DP

注意: None

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	#define N 6005
	#define clr(x,v) memset(x,v,sizeof(x))
	struct tNode {
	int chi, bro;
	int val;
	tNode( int _chi = 0, int _bro = 0, int _val = 0 ): chi(_chi), bro(_bro), val(_val) {}
	};
	int n;
	tNode tree[N];
	int dp[N][2];
	bool ch[N];
	const int solve( const int now, const int vis )
	{
	if( dp[now][vis] != -1 ) return dp[now][vis];
	int i;
	dp[now][vis] = (vis?tree[now].val:0);
	if( vis ) {
	for( i = tree[now].chi; i; i = tree[i].bro ) {
	dp[now][vis] += solve( i, 0 );
	}
	} else {
	for( i = tree[now].chi; i; i = tree[i].bro ) {
	dp[now][vis] += max( solve( i, 1 ), solve( i, 0 ) );
	}
	}
	return (dp[now][vis]);
	}
	int main( void )
	{
	int i, j;
	int f, c, grandpa;
	while( scanf( "%d", &n ) == 1 && n ) {
	for( i = 1; i <= n; ++i ) {
	tree[i] = tNode(0);
	scanf( "%d", &tree[i].val );
	}
	clr(ch,0);
	while( scanf( "%d%d", &c, &f ) == 2 && (c||f) ) {
	ch[c] = 1;
	if( !tree[f].chi ) tree[f].chi = c;
	else {
	j = tree[f].chi;
	while( tree[j].bro ) j = tree[j].bro;
	tree[j].bro = c;
	}
	}
	for( grandpa = 1; ch[grandpa]; ++grandpa );
	clr(dp,-1);
	printf( "%d\n", max(solve(grandpa,0),solve(grandpa,1)) );
	}
	return 0;
	}

view raw Anniversary party hosted with ❤ by GitHub