题目

略

分析

又是一个显然的树形依赖背包

然而可以 \(O(nm)\) 依靠 \(dfs\) 序来 \(dp\)

\(Code\)

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 2005;

int v[N] , p[N] , f[N][10005] , n , m , tot , h[N] , dfn[N] , dfc , siz[N];

struct edge{

	int to , nxt;

}e[N * 2 + 5];

void add(int x , int y){e[++tot] = edge{y , h[x]} , h[x] = tot;}

void dfs(int x , int fa)

{

	dfn[++dfc] = x , siz[x] = 1;

	for(register int i = h[x]; i; i = e[i].nxt)

	{

		int y = e[i].to;

		if (y == fa) continue;

		dfs(y , x);

		siz[x] += siz[y];

	}

}

int main()

{

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

	int x , y;

	for(register int i = 1; i <= n; i++) scanf("%d%d" , &v[i] , &p[i]);

	for(register int i = 1; i < n; i++) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);

	dfs(1 , 0);

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

		for(register int j = m; j >= 0; j--)

		{

			if (j >= p[dfn[i]]) f[i][j] = max(f[i][j] , f[i + 1][j - p[dfn[i]]] + v[dfn[i]]);

			f[i][j] = max(f[i][j] , f[i + siz[dfn[i]]][j]);

		}

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

}

巴特西

JZOJ 5344. 【NOIP2017模拟9.3A组】摘果子

题目

分析

\(Code\)

最新文章

热门文章