洛谷 P1273 有线电视网 && caioj 1109 树形动态规划（TreeDP）4：比赛转播（树上分组背包总结）

从这篇博客往前到二叉苹果树都可以用分组背包做

这依赖性的问题，都可以用于这道题类似的方法来做

$f[i][j]%u8868%u793A$ 表示以i为根的树中取j个节点所能得的最大价值

那么每一个子树可以看成一个组，每个组里面取一个节点，两个节点，三个节点就是三个不同的物品

对于这道题，有

$f[i][j] = max( f[i][j-k] + f[v][k] - w);$

我们来类比一下普通分组背包的转移方程 $f[k][j] = max(f[k-1][j], f[k-1][j-w[i]]+p[i])$

这里的k表示第几组，而在树上就直接用i表示，因为i已经包含它的子树的信息了

然后 $f[i][j-k]$ 相当于 $f[k-1][j-w[i]]$ ，后面的 $f[v][k] - w$ 相当于 $p[i]$

然后注意k不能等于0，因为k=0就不会减去w了，本身的值就是k=0的情况

#include<cstdio>

#include<vector>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 3123;

int f[MAXN][MAXN], cnt[MAXN], n, m;

struct node { int v, w; };

vector<node> g[MAXN];

void dfs(int u, int fa)

{

	REP(i, 0, g[u].size())

	{

		int v = g[u][i].v, w = g[u][i].w;

		if(v == fa) continue;

		dfs(v, u);

		cnt[u] += cnt[v];

		for(int j = cnt[u]; j >= 1; j--)

			REP(k, 1, min(j, cnt[v]) + 1)

				f[u][j] = max(f[u][j], f[u][j-k] + f[v][k] - w);

	}

}

int main()

{

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

	REP(u, 1, n - m + 1)

	{

		int k, v, w;

		scanf("%d", &k);

		REP(i, 0, k)

		{

			scanf("%d%d", &v, &w);

			g[u].push_back(node{v, w});

		}

	}

	memset(f, 0xc0, sizeof(f));

	REP(i, 1, n + 1) f[i][0] = 0;

	REP(i, n - m + 1, n + 1)

	{

		cnt[i] = 1;

		scanf("%d", &f[i][1]);

	}

	dfs(1, 0);

	for(int i = m; i >= 0; i--)

		if(f[1][i] >= 0)

		{

			printf("%d\n", i);

			break;

		}

	return 0;

}

巴特西

洛谷 P1273 有线电视网 && caioj 1109 树形动态规划（TreeDP）4：比赛转播（树上分组背包总结）

最新文章

热门文章