有个公司要举行一场晚会。
为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司
（上司的上司，上司的上司的上司……都可以邀请）。
每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。
input：
第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。
output：
一个数，最大的气氛值和。
input：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
output：
5
分析：
f[i,1]表示邀请i的最大值 f[i,2]表示不邀请i的最大值
f[i,1]=sigma(f[i.sons,2]) f[i,2]=sigma(max{f[i.sons,1],f[i.sons,2]})
这个又是树型动态规划的一种分类，每个结点都有二种状态既选与不选。
【参考程序】：
#include<iostream>
using namespace std;
int f[6001][2],father[6001];
bool v[6001];
int n;
int find_max(int a,int b)
{
if (a>b) return a;
else return b;
}
void dfs(int k)
{
v[k]=false;
for (int i=1;i<=n;i++)
if (v[i] && father[i]==k)
{
dfs(i);
f[k][0]+=f[i][1];
f[k][1]+=find_max(f[i][0],f[i][1]);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&f[i][0]);
int l,k,root;
root=0;bool bk=true;
while (scanf("%d%d",&l,&k),l+k>0)
{
father[l]=k;
if (root==l || bk==true)
{
root=k;bk=false;
}
}
memset(v,true,sizeof(v));
dfs(root);
printf("%d\n",find_max(f[root][0],f[root][1]));
return 0;
}
【参考程序】：
#include<iostream>
using namespace std;
int f[2][6001],now[6001],pre[6001],child[6001];
int n;
int Max(int a,int b)
{
if (a>b) return a;
else return b;
}
void dfs(int k)
{
while (now[k])
{
dfs(child[now[k]]);
f[0][k]+=f[1][child[now[k]]];
f[1][k]+=Max(f[0][child[now[k]]],f[1][child[now[k]]]);
now[k]=pre[now[k]];
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&f[0][i]);
pre[i]=child[i]=now[i]=0;
}
int root,k,l;
root=(n+1)*n/2;
for (int i=1;i<=n-1;i++)
{
scanf("%d%d",&l,&k);
child[i]=l;pre[i]=now[k];
now[k]=i;root-=l;
}
dfs(root);
printf("%d\n",Max(f[0][root],f[1][root]));
return 0;
}