[Ural] 1018 Binary Apple Tree

題目網址: http://acm.timus.ru/problem.aspx?num=1018

題意: 給定一顆二叉樹，每枝樹枝上都包含Ni個蘋果(1<=i<=N)，問最後要保留Q枝樹枝，蘋果數量最大。



解法: 令dp[i][j]代表以第i個節點為樹根的子樹，砍掉j根樹枝後，所保留最多的蘋果數量，狀態轉移方程(遞迴關係式):

當要砍的枝數等於當前節點的枝數，則能保留的最多蘋果數為0；否則，考慮所有砍樹枝的情況，求最大為保留最多的蘋果數。

dp[i][j] = { 0,if j == tree[i].cnt(包含節點i的樹枝總數)
           { max{ dp[tree[i].l][k]+dp[tree[i].r][j-k] }, for 0 <= k <= j, if k <= tree[tree[i].l].cnt && (j-k) <= tree[tree[i].r].cnt

答案為 dp[1][N-1-Q]。

*tree[i].r(tree[i].l) is the right(left) child of tree[i]

TAG: DP, Tree DP

注意: None

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	#define N 105
	#define clr(x,v) memset( x, v, sizeof(x) )
	struct tNode {
	int l, r, f;
	int cnt, val;
	tNode( int _l = 0, int _r = 0, int _f = 0, int _cnt = 1, int _val = 0 )
	: l(_l), r(_r), f(_f), cnt(_cnt), val(_val) {}
	};
	int n, q;
	int e[N][5];
	int v[N][5];
	int cnt[N];
	int dp[N][N];
	tNode tree[N];
	bool vis[N];
	const int solve( const int now, const int cnum )
	{
	if( dp[now][cnum] != -1 ) return dp[now][cnum];
	if( cnum == tree[now].cnt ) return (dp[now][cnum] = 0);
	int i, l = tree[now].l, r = tree[now].r;
	dp[now][cnum] = 0;
	for( i = 0; i <= cnum; ++i ) if( i <= tree[l].cnt && (cnum-i) <= tree[r].cnt ) {
	dp[now][cnum] = max( dp[now][cnum], solve(l,i)+solve(r,cnum-i)+tree[now].val );
	}
	return dp[now][cnum];
	}
	const int buildtree( const int now, const int fat, const int val )
	{
	int i;
	vis[now] = true;
	bool flag = true;
	tree[now] = tNode();
	tree[now].f = fat;
	tree[now].val = val;
	for( i = 0; i < cnt[now]; ++i ) if( !vis[e[now][i]] ) {
	if( flag ) { tree[now].l = e[now][i]; flag = false; }
	else tree[now].r = e[now][i];
	tree[now].cnt += buildtree( e[now][i], now, v[now][i] );
	}
	return tree[now].cnt;
	}
	int main( void )
	{
	int i;
	int a, b, c;
	while( scanf( "%d%d", &n, &q ) == 2 ) {
	clr(e,0);
	clr(cnt,0);
	clr(vis,0);
	clr(dp,-1);
	for( i = 1; i < n; ++i ) {
	scanf( "%d%d%d", &a, &b, &c );
	v[a][cnt[a]] = v[b][cnt[b]] = c;
	e[a][cnt[a]++] = b;
	e[b][cnt[b]++] = a;
	}
	buildtree( 1, 0, 0 );
	tree[0].cnt = 0;
	printf( "%d\n", solve(1,(n-1)-q) );
	}
	return 0;
	}

view raw Binary Apple Tree hosted with ❤ by GitHub