蓝桥杯训练:动态规划——没有上司的晚会

xiaoxiao2021-02-28  108

题目描述   Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别,可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号(范围在1到N之间),并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐,校长想设法使每个职员和他(她)的直接上司不会同时参加聚会。   你的任务是设计一份参加聚会者的名单,使总的欢乐度最高。 输入格式   输入的第一行是一个整数N,1<= N <= 6000   以下的N行是对应的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 来源:网上代码加自己修改BUG,源码地址:http://blog.csdn.net/libin56842/article/details/9814455 完成时间:2017年8月23日 作者:何知令

解题思想:找出所有的根节点,再依次访问他所有的根节点,动态的记录该节点代表员工去和不去的高兴度,最终汇合到其根节点上来,最终把根节点加起来便是所求的答案

代码如下:

/* 题目描述   Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别,可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号(范围在1到N之间),并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐,校长想设法使每个职员和他(她)的直接上司不会同时参加聚会。   你的任务是设计一份参加聚会者的名单,使总的欢乐度最高。 输入格式   输入的第一行是一个整数N,1<= N <= 6000   以下的N行是对应的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 来源:网上代码加自己修改BUG,源码地址:http://blog.csdn.net/libin56842/article/details/9814455 完成时间:2017年8月23日 作者:何知令 解题思想:找出所有的根节点,再依次访问他所有的根节点,动态的记录该节点代表员工去和不去的高兴度,最终汇合到其根节点上来,最终把根节点加起来便是所求的答案 */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int father[6005],vis[6005],dp[6005][2],t; void dfs(int node) { int i; vis[node] = 1; for(i = 1; i<=t; i++) { if(!vis[i] && father[i] == node) { dfs(i); dp[node][1]+=dp[i][0];//node去,则i必不能去 dp[node][0]+=max(dp[i][0],dp[i][1]);//node不去,取i去或不去的最大值 } } } int main() { int i,l,k; int sum=0; scanf("%d",&t); for(i = 1; i<=t; i++) scanf("%d",&dp[i][1]); while(scanf("%d%d",&l,&k),l+k>0) { father[l] = k;//记录上司 } memset(vis,0,sizeof(vis)); for(i=1; i<=t; i++) if(father[i]==0) { dfs(i); sum+=max(dp[i][1],dp[i][0]); } printf("%d\n",sum); return 0; } 程序运行结果展示:

知识点总结:动态规划

学习心得:网上代码加改BUG

转载请注明原文地址: https://www.6miu.com/read-64074.html

最新回复(0)