首页 > 代码库 > [vijos]P1642 班长的任务
[vijos]P1642 班长的任务
背景
十八居士的毕业典礼（1）
描述
福州时代中学2009届十班同学毕业了，于是班长PRT开始筹办毕业晚会，但是由于条件有限，可能每个同学不能都去，但每个人都有一个权值，PRT希望来的同学们的权值总和最大。
十班有一个周密的电话通知网络，它其实就是一棵树，根结点为班长PRT，由她来负责通知她的下线（也就是儿子节点），下线们继续通知自己的下线（不一定每个下线都要通知），任何人都可以不去：”
为了使权值总和最大，班长想安排一下人，但是人数很多，人脑是难以应付的，所以她找到十八居士，让他编程用电脑解决。
格式
输入格式
输入第一行两个整数n，m表示有n位同学，至多只能去m位同学。(1<=m<=n)
接下来2*n行，每两行代表一个同学的信息（如果这位同学没有子节点，就只有一行）。
每个同学的第一行两个整数p，s，表示这位同学权值为p，子节点个数s；(-100<=p<=100)
第二行s个整数，表示这位同学的子节点的编号。
班长的编号一定为1。
对于20%数据1<=n<=10
对于60%数据1<=n<=100
对于100%数据1<=n<=1000
输出格式
输出一个整数，表示权值的最大值。
样例1
样例输入1[复制]
8 5100 22 379 24 5109 36 7 8100 0100 0100 0101 0108 0
样例输出1[复制]
518
提示
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 const int INF=0x7fffffff; 6 7 int n,m; 8 int v[1001],s[1001],a[1001][1001]; 9 int f[1001][1001];10 int list[1001],Count[1001],q;11 12 int tree_traversal(int k)13 {14 list[++q]=k;15 if(s[k]==0) return ++Count[k];16 for(int i=1;i<=s[k];i++)17 Count[k]+=tree_traversal(a[k][i]);18 return ++Count[k];19 }20 21 int main()22 {23 memset(f,0x8f,sizeof(f));24 cin>>n>>m;25 for(int i=1;i<=n;i++)26 {27 int t;28 cin>>v[i]>>t;29 while(t--)30 cin>>a[i][++s[i]];31 }32 tree_traversal(1);33 for(int i=1;i<=n;i++)34 {35 f[i][0]=0;36 f[i][1]=v[list[i]];37 }38 for(int i=n-1;i>=0;i--)39 for(int j=1;j<=m;j++)40 f[i][j]=max(f[i+1][j-1]+v[list[i]],f[i+Count[list[i]]][j]);41 int ans=-INF;42 for(int i=0;i<=m;i++)43 ans=max(ans,f[1][i]);44 cout<<ans;45 }
[vijos]P1642 班长的任务
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。