题意

给出一个n个结点的树，给出n-1个度的权值f[]，代表如果一个点的度数为i，那么它对于答案的贡献有f[i]。问在这棵树最大的贡献能达到多少。

思路

对于这个图，有n*2-2个度可以分配（看成一条链的形状），首先可以确定n个点，那么每个点都是要分配一个度的，因此现在有n个f[1]，还有n-2个度没有分配。那么这n-2就可以当做背包容量，对于每一种度，像完全背包一样去枚举用多少种最优。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int N = 1e4 + 11;

int f[N], dp[N];

int main() {

	int n, t; scanf("%d", &t);

	while(t--) {

		scanf("%d", &n);

		memset(dp, -INF, sizeof(dp));

		dp[0] = 0;

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

		for(int i = 1; i < n - 1; i++) // 有n-2种物品分配,每个物品可以用无限次,这里偏移了1,实际上只用2至n-1

			for(int j = i; j < n - 1; j++) // 背包最大容量为n-2,像完全背包一样枚举

				dp[j] = max(dp[j], dp[j-i] + f[i+1] - f[1]); // 将1号结点换成i号结点

		printf("%d\n", dp[n-2] + n * f[1]);

	}

	return 0;

}

巴特西

HDU 5534：Partial Tree（完全背包）***

题意

思路

最新文章

热门文章