2811_摘Galo_dp

发布于 2017-10-30  827 次阅读

题目描述

0v0在野外看到了一棵Galo树，看到食物的0v0瞪大了眼睛，变成了OvO。 
这棵Galo树可以看做是一棵以1号点为根的n个点的有根数，除了根节点以外，每个节点i都有一个Galo，美味度为w[i]。 
OvO发现，如果她摘下了i号Galo，那么i的子树中的Galo以及i到根的路径上的其他Galo都会死掉。 
OvO的袋子只能装k个Galo，她的嘴巴里还能叼1个，请问她所摘Galo的美味度之和的最大值是多少？

 

思路

题目可以转化为选若干个子树没有公共部分的点然后求最大值，

这样我们就可以将树变成一个dfs序列，求出若干个不相交的序列的最大值

这样我们可以dp,设f[i][j]为前i个数选了j段的最大值

f[i][j]=max{f[i - 1][j], f[i - len[i]][j-1]}

然后我们可以滚一维即可

#include 
#include 
#include 
#include 
using namespace std;
#define N 220001
#define fill(x, y) memset(x, y, sizeof(x))
#define LL long long
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
struct edge
{
	int to, next;	
}e[N];
int ls[N], st[N], ed[N], a[N], rec[N], size[N];
LL f[2][N];
int maxE = 0;
int add(int x, int y)
{
	e[++maxE] = (edge) {y, ls[x]};
	ls[x] = maxE;
}
int num = 0;
int dfs(int now)
{
	num++;
	rec[num] = now;
	size[now] = 1;
	for (int i = ls[now]; i; i = e[i].next)
	{
		dfs(e[i].to);
		size[now] += size[e[i].to];
	}
}
int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	k++;
	for (int i = 2; i <= n; i++)
	{
		int fa, w;
		scanf("%d%d", &fa, &a[i]);
		add(fa, i);
	}
	dfs(1);
	LL ans = 0;
	for (int j = 0; j <= k; j++)
	{
		fill(f[(j + 1) & 1], 0);
		for (int i = 1; i <= n; i++)
		{
			f[j & 1][i + 1] = max(f[j & 1][i + 1], f[j & 1][i]);
			if (j < k)
			{
				f[(j + 1) & 1][i + size[rec[i]]] = max(f[(j + 1) & 1][i + size[rec[i]]], f[j & 1][i] + a[rec[i]]);
				ans = max(ans, f[(j + 1) & 1][i + size[rec[i]]]);
			}
			ans = max(ans, f[j & 1][i + 1]);
		}
	}
	cout << ans << endl;
}

　　

]]>