首页 > 代码库 > [HDOJ5534] Partial Tree（脑洞，完全背包）

[HDOJ5534] Partial Tree（脑洞，完全背包）

2024-09-20 14:21:25   220人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534

题意：给n个点，希望用这n个点构成一棵树，然后每一个度有一个价值，希望价值总和最大。问最大价值。

知道一棵树的度和为2*n-2，并且每一个点必然有1的度，在每个点持有1度的情况下，相当于给n个点分n-2个度。试验发现，无论如何分配，都可以构成一棵树。

这样问题就变成了容量为n-2的背包，有2~n-2个物品，价值分别为v(i)的完全背包问题。

先让所有价值减去度为1的价值，做完全背包后再加回去。注意做完全背包的时候要默认度为1，所以转移为dp[i] = max(dp[i], dp[i-j]+v[j+1])。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 2020;
 5 int n;
 6 int v[maxn];
 7 int dp[maxn];
 8 
 9 int main() {
10     // freopen("in", "r", stdin);
11     int T;
12     scanf("%d", &T);
13     while(T--) {
14         scanf("%d", &n);
15         for(int i = 1; i < n; i++) {
16             scanf("%d", &v[i]);
17             if(i != 1) v[i] -= v[1];
18         }
19         for(int i = 1; i <= n - 2; i++) dp[i] = -0x7f7f7f7f;
20         dp[0] = 0;
21         for(int i = 1; i <= n - 2; i++) {
22             for(int j = 1; j <= i; j++) {
23                 dp[i] = max(dp[i], dp[i-j]+v[j+1]);
24             }
25         }
26         printf("%d\n", dp[n-2]+n*v[1]);
27     }
28     return 0;
29 }

 

[HDOJ5534] Partial Tree（脑洞，完全背包）


联系
我们