「vijos1642」班长的任务

2014年1月2日3,7700

背景

十八居士的毕业典礼（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[复制]

8 5 100 2 2 3 79 2 4 5 109 3 6 7 8 100 0 100 0 100 0 101 0 108 0

1
2
3
4
5
6
7
8
9
10
11
12

8 5
100 2
2 3
79 2
4 5
109 3
6 7 8
100 0
100 0
100 0
101 0
108 0

样例输出1[复制]

518

1

518

代码

正常做法80分

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,v[1001],f[1001][1001];
struct data
{
int l,r;
}a[1005];
void insert(int w,int c)
{
	int p=a[w].l;
	if(a[w].l==0)a[w].l=c;
	else
	   {
          while(a[p].r!=0)p=a[p].r;
	      a[p].r=c;
	   }
}
void doit(int w,int sh)
{
	int p;
	if(w==0||sh==0){f[w][sh]=0;return;}
	if(f[w][sh]!=-1)return;
	doit(a[w].r,sh);
	f[w][sh]=f[a[w].r][sh];
	for(int k=0;k<sh;k++)
	   {
              doit(a[w].l,k); 
              doit(a[w].r,sh-1-k);
	      f[w][sh]=max(f[w][sh],f[a[w].l][k]+f[a[w].r][sh-1-k]+v[w]);
	   }
}
int main()
{
	int s;
	scanf("%d%d",&n,&m); 
    memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++)
	   {
            scanf("%d%d",&v[i],&s);
	    while(s--)
	       {
                  int t;
		  scanf("%d",&t);
                  insert(i,t);
		   }
	   }
	doit(1,m);
	printf("%d",f[1][m]);
	return 0;
}

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

using namespace std;

int n,m,v[1001],f[1001][1001];

struct data

{

int l,r;

}a[1005];

void insert(int w,int c)

{

int p=a[w].l;

if(a[w].l==0)a[w].l=c;

else

{

while(a[p].r!=0)p=a[p].r;

a[p].r=c;

}

void doit(int w,int sh)

{

int p;

if(w==0||sh==0){f[w][sh]=0;return;}

if(f[w][sh]!=-1)return;

doit(a[w].r,sh);

f[w][sh]=f[a[w].r][sh];

for(int k=0;k<sh;k++)

{

doit(a[w].l,k);

doit(a[w].r,sh-1-k);

f[w][sh]=max(f[w][sh],f[a[w].l][k]+f[a[w].r][sh-1-k]+v[w]);

}

int main()

{

int s;

scanf("%d%d",&n,&m);

memset(f,-1,sizeof(f));

for(int i=1;i<=n;i++)

{

scanf("%d%d",&v[i],&s);

while(s--)

{

int t;

scanf("%d",&t);

insert(i,t);

}

doit(1,m);

printf("%d",f[1][m]);

return 0;

}

优解（m*n）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int v[1001],s[1001],a[1001][1001];
int f[1001][1001];
int list[1001],count[1001],q;
int tree_traversal(int k)
{
    list[++q]=k;
    if(s[k]==0){return ++count[k];}
    for(int i=1;i<=s[k];i++)count[k]+=tree_traversal(a[k][i]);
    return ++count[k];
}
int main()
{
    memset(f,-127,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
       {
              int t;scanf("%d%d",&v[i],&t);
              while(t--)scanf("%d",&a[i][++s[i]]);
       }
    tree_traversal(1);
    for(int i=1;i<=n;i++){f[i][0]=0;f[i][1]=v[list[i]];}
    for(int i=n-1;i>=0;i--)
       for(int j=1;j<=m;j++)
    {
        f[i][j]=max(f[i+1][j-1]+v[list[i]],f[i+count[list[i]]][j]);
    }
    int ans=-999999;
    for(int i=1;i<=m;i++)ans=max(ans,f[1][i]);
    printf("%d",max(ans,0));
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

int v[1001],s[1001],a[1001][1001];

int f[1001][1001];

int list[1001],count[1001],q;

int tree_traversal(int k)

{

list[++q]=k;

if(s[k]==0){return ++count[k];}

for(int i=1;i<=s[k];i++)count[k]+=tree_traversal(a[k][i]);

return ++count[k];

}

int main()

{

memset(f,-127,sizeof(f));

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

int t;scanf("%d%d",&v[i],&t);

while(t--)scanf("%d",&a[i][++s[i]]);

}

tree_traversal(1);

for(int i=1;i<=n;i++){f[i][0]=0;f[i][1]=v[list[i]];}

for(int i=n-1;i>=0;i--)

for(int j=1;j<=m;j++)

{

f[i][j]=max(f[i+1][j-1]+v[list[i]],f[i+count[list[i]]][j]);

}

int ans=-999999;

for(int i=1;i<=m;i++)ans=max(ans,f[1][i]);

printf("%d",max(ans,0));

return 0;

}

参考论文《浅谈数据的合理组织》

« 「CODEVS1380」没有上司的舞会「BZOJ1040」[ZJOI2008] 骑士 »

hzwer.com _ Home | http://hzwer.com

「vijos1642」班长的任务

背景

描述

输入格式

输出格式

样例输入1[复制]

样例输出1[复制]

代码

分类目录

热门文章

Myfriends

近期评论