【问题描述】
有个公司要举行一场晚会。为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司（上司的上司，上司的上司的上司……都可以邀请）。每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。所有员工的编号为1～N。
【输入格式】
第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示K是 L的上司。
输入以0 0结束。
【输出格式】
一个数，最大的气氛值和。
【输入样例】
7
1 1 1 1 1 1 1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
【输出样例】5
【解析】
这道题..
不知道说什么.. 一开始出于习惯瞬间把森林转二叉树打完了..
结果发现根本不用..
只需要用f[i][0]和f[i][1]来存状态..
f[i][0]表示不请i的最大收益
f[i][1]表示请i的最大收益
知道这两个状态就ok了..
然后就TreeDP吧
void Tree_DP ( int x ){if ( f[x][0] != -1 || f[x][1] != -1 ) return;if ( x < 0 ) return;int i, j, k, f1, f0;f0 = 0; f1 = w[x];for ( k = first[x]; k; k = a[k].next ){Tree_DP (a[k].y);f1 += f[a[k].y][0];f0 += _max ( f[a[k].y][0], f[a[k].y][1] );}f[x][0] = f0; f[x][1] = f1;
}【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int w[6100], n;
struct edgenode {int x, y, next;
}a[6100]; int first[6100], len;
void ins ( int x, int y ){len ++;a[len].x = x; a[len].y = y;a[len].next = first[x]; first[x] = len;
}
int f[6100][2];
bool v[6100];
int _max ( int x, int y ){ return x > y ? x : y; }
void Tree_DP ( int x ){if ( f[x][0] != -1 || f[x][1] != -1 ) return;if ( x < 0 ) return;int i, j, k, f1, f0;f0 = 0; f1 = w[x];for ( k = first[x]; k; k = a[k].next ){Tree_DP (a[k].y);f1 += f[a[k].y][0];f0 += _max ( f[a[k].y][0], f[a[k].y][1] );}f[x][0] = f0; f[x][1] = f1;
}
int main (){int i, j, k, x, y;scanf ( "%d", &n );for ( i = 1; i <= n; i ++ ) scanf ( "%d", &w[i] );memset ( v, false, sizeof (v) );while ( scanf ( "%d%d", &x, &y ) && x != 0 || y != 0 ){ins ( y, x ); v[x] = true;}for ( i = 1; i <= n; i ++ ){if ( v[i] == false ){ins ( 0, i );}}memset ( f, -1, sizeof (f) );Tree_DP (0);printf ( "%d\n", f[0][0] );return 0;
}