年会 （记忆化搜索+二叉树思想）------------------------------C语言—菜鸟级

时间限制: 1Sec 内存限制: 128MB 提交: 54 解决: 24

题目描述
背景
某大学校长准备开一次年会. 该校的员工具有等级结构, 即师生关系构成一棵树, 以校长为树根. 员工号是1到N之间的整数. 人事部门把所有员工按活跃度排序. 为了让年会使所有参加者都玩的高兴, 校长不想让任何一个员工和他/她的直接导师同时被邀请.

你的任务是列一张客人名单, 以使客人活跃度最大.

输入
第1行是一个整数N. 1 ≤ N ≤ 6000.
接着的N行包含相应员工的活跃度.活跃度是一个-128到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

//思路： 记忆化搜索 + 二叉树
//常理来说大学里 一个导师可以有多个学员 但一个学员只能有一个导师（二叉树）
// 导师和学员不能同时邀请，那就是除了同时邀请外 还有三种情况，邀导不邀学
//邀学不邀导 和都不邀 （0与1 ）的关系 通过DFS枚举各类情况，优化记忆数组； 
#include <string.h>
#include <stdio.h>
#define M 6002
#define max(a,b) a>b?a:b
int n;
int v[M]; 
int bj[M];
//标记非根节点（将有学员身份的员工或者学员标记）
//没标记的就只有导师身份（即根节点） 
int ds[M][15];
//导师数组 ds[i][j]=4；代表第i个人作为导师身份时第j个学员为4号学员 
int dp[M][2];//记忆数组dp[L][0]代表满足条件下该员工（L）的导师未邀请状态最优活跃度
             // dp[L][1]代表满足条件下该员工(L)的导师邀请状态下最优活跃度
int dfs(int L,int last)
{   //优化 记忆数组 
    if(dp[L][last]!=-1)return dp[L][last];
	if(!ds[L][0])//表示 当前员工无学员 即 该员工只有学员身份 
	{ if(last==0&&v[L]>0)return v[L];//若该员工的导师未邀请且该学员可i活跃气氛 
	  else return 0;//不活跃当然不能要； 
	}
    int ans1=0, ans2=0,i;
   //若不邀请该员工 就去找该员工的学员（下一层节点）的最优解 
    i=0;while(ds[L][i]!=0)ans1+=dfs(ds[L][i],0),i++;
     //若该员工的导师没被邀请 并且邀请该员工 然后去找该员工的学员（下一层节点）的最优解 
	if(last!=1)i=0;while(ds[L][i]!=0)ans2+=dfs(ds[L][i],1),i++;
        
       if(last==0)//若该员工的导师未邀请  
		{dp[L][0]=max(ans1,ans2+v[L]);
		//该节点的最优解为（邀请该员工 与不邀请的该员工的）最大值 
		//（即可能 该员工和他导师活跃值为负 都不邀请滴好） 
		  return dp[L][0];
		}//若该员工的导师邀请 ，那该员工只能不邀请 
		  dp[L][1]=ans1;
		  return dp[L][1];
		
}

int main()
{ int i,l,k,j,ans=0;
     scanf("%d",&n);
    memset(bj,0, sizeof(bj));
    memset(ds,0, sizeof(ds)); 
    memset(dp,-1,sizeof(dp));
    for(i=1;i<=n;i++)
    scanf("%d",&v[i]);
    while(1)
	{    
	   scanf("%d%d",&l,&k);
	    if(l==0&&k==0)break;
        j=0;
        while(ds[k][j]!=0)j++;//给l学员在他导师那找个序号位置 
		ds[k][j]=l;
        bj[l]=1;//标记该员工有学员身份 
    }
    for(i=1;i<=n;i++)//枚举根节点（ 只有导师身份的人） 
    if(!bj[i])ans+=dfs(i,0);//把各各没有关系的导师集合的最优解加起来 
    printf("%d\n",ans);
    return 0;
}


  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80727026