树形DP
所有DP的思想应该都是一样的 只是换了形式而已
用邻接表储存领导和下属的关系 表头表示领导
从树根开始递归 以叶子节点为截止点
joinsum[i] 表示 第 i 个人参加时最大高兴值 若i参加 他的下属则不能参加
unjoinsum[i] 表示 第 i 个人不参加的最大高兴值 若i不参加 他的下属有参加和不参加
两种情况 选较大的情况
http://acm.timus.ru/problem.aspx?space=1&num=1039
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
long joinsum[6001];
long unjoinsum[6001];
int happy_value[6001];//第 n 个人的高兴值
bool had[6001];//用来记录树根
struct node
{
struct tt *next;
}mem[6001];
struct tt
{
int k;
struct tt *next;
};
inline void build(int i,int j)
{
struct tt *t=new tt;
t->k=j;
t->next=mem[i].next;
mem[i].next=t;
}
long dpout(int );
long dpin(int i)//第 i 个人参加
{
if(joinsum[i]!=-1)
return joinsum[i];
if(mem[i].next==NULL)//i为 叶子
{
joinsum[i]=happy_value[i];
return joinsum[i];
}
if(mem[i].next!=NULL)
{
struct tt *t=mem[i].next;
joinsum[i]=happy_value[i];
while(t!=NULL)
{
joinsum[i]+=dpout(t->k);//下属不能参加
t=t->next;
}
return joinsum[i];
}
}
long dpout(int i)//第 i 个人不参加
{
if(unjoinsum[i]!=-1)
return unjoinsum[i];
if(mem[i].next==NULL)//i为 叶子
{
unjoinsum[i]=0;
return unjoinsum[i];
}
if(mem[i].next!=NULL)
{
unjoinsum[i]=0;
struct tt *t=mem[i].next;
while(t!=NULL)
{
unjoinsum[i]+=max(dpin(t->k),dpout(t->k));//下属可参加 可不参加
t=t->next;
}
return unjoinsum[i];
}
}
int main()
{
//freopen("D:\\6\\bin\\Debug\\hu.txt","r",stdin );
int n,i,up,down;
long l1,l2;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",happy_value+i);
memset(had,false,sizeof(had));//初始化全为根
while(scanf("%d%d",&down,&up))
{
if(!down&&!up)
break;
had[down]=true;//down 不是根
build(up,down);
}
for(i=1;i<=n;i++)
{
if(!had[i])//i 为树根
break;
}
memset(joinsum,-1,sizeof(joinsum));
memset(unjoinsum,-1,sizeof(unjoinsum));
l1=dpin(i);//i 参加的最大高兴值
l2=dpout(i);//i 不参加的最大高兴值
if(l1>l2)
printf("%ld\n",l1);
else
printf("%ld\n",l2);
return 0;
}