博客

题目：

题目描述
czy要召集他的妹子，但是由于条件有限，可能每个妹子不能都去，但每个妹子都有一个美丽值，czy希望来的妹子们的美丽值总和最大（虽然……）。 czy有一个周密的电话通知网络，它其实就是一棵树，根结点为czy，他可以通知一些妹子（毕竟他不认识他的所有妹子嘛），称为他的下线（也就是儿子节点），下线们继续通知自己的下线。任何妹子都可以不去，但是任何一个妹子如果要去，则她的上线（也就是她的父亲节点）一定要去。 为了使妹子美丽值总和最大，czy想安排一下，（非强制）让一些妹子去。但是妹子数很多，人脑是难以应付的，所以他想让你用电脑解决。

输入输出格式
输入格式：
输入第一行两个整数n，m表示有n个妹子，至多只能去m个妹子。(1<=m<=n) 接下来2*n行，每两行代表一个妹子的信息（如果这个妹子没有子节点，就只有一行）。 每个妹子的第一行两个整数p，s，表示这个妹子美丽值为p，子节点个数s；(-100<=p<=100) 第二行s个整数，表示这个妹子的子节点的编号。czy的编号一定为1。

输出格式：
输出一个整数，表示权值的最大值。

输入输出样例
输入样例#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： 
518
说明
对于20%数据1<=n<=10

对于60%数据1<=n<=100

对于100%数据1<=n<=1000

思路：

浅谈数据的合理组织

hzwer的博客

先对树进行先序遍历，将结果存在lst数组中。

设cnt[i]表示i的子节点个数+1，那么在lst数组中，可见i的下一个兄弟节点在lst中的编号为i+cnt[i]。

设f[i][j]表示只考虑i~n的妹子，在其中选j个妹子取所得的最大美丽值。

假如不选第i个妹子，那么第i+1~i+cnt[i]-1的妹子也不用考虑了，此时f[i][j] = f[i+ cnt[lst[i]]] [j]。

假如选第i个妹子，那么就需要加上第i个妹子的美丽值，以及在i+1~n个妹子中选j个妹子的最大美丽值，此时f[i][j]= f[i+1][j-1]+v[lst[i]]。

所以状态转移方程：f[i][j]=max(f[i+1][j-1]+v[lst[i]],f[i+cnt[lst[i]]][j])。

代码：

#include<bits/stdc++.h>
using namespace std;

#define maxn 1000
#define inf (1<<30)

int n,m;
int v[maxn+5];
vector<int> a[maxn+5];

int lst[maxn+5]={0},q=0;
int cnt[maxn+5]={0};

int f[maxn+5][maxn+5]={0};

int dfs(int x){
	lst[++q]=x;
	if(!a[x].size()) return ++cnt[x];
	for(int i=0;i<a[x].size();i++){
		cnt[x]+=dfs(a[x][i]);
	}
	return ++cnt[x];
}

void init(){
	for(int i=1;i<=n;i++){
		for(int j=2;j<=m;j++){
			f[i][j]=-inf;
		}
		f[i][1]=v[lst[i]];
	}
}

int main(){
	scanf("%d%d",&n,&m); 
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d%d",&v[i],&x);
		while(x--){
			int y;
			scanf("%d",&y);
			a[i].push_back(y);
		}
	}
	
	dfs(1);
	init();
	
	for(int i=n;i>=1;i--){
		for(int j=1;j<=m;j++){
			f[i][j]=max(f[i+1][j-1]+v[lst[i]],f[i+cnt[lst[i]]][j]);
		}
	}
	
	int ans=0;
	for(int i=1;i<=m;i++){
		ans=max(ans,f[1][i]);
	}
	printf("%d",ans);
	
	return 0;
}