首页 > 代码库 > HDU 5534 Partial Tree (完全背包变形)
HDU 5534 Partial Tree (完全背包变形)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534
题意：
给你度为1 ~ n - 1节点的权值，让你构造一棵树，使其权值和最大。
思路：
一棵树上每个节点的度至少为1，且度的和为2*n - 2。那么我们先给这些节点的度都-1，剩下的节点度为n - 2。此时我们发现，任意分配剩下的这些度给节点，都可以形成一棵树。这就变成了一个完全背包题，容量为n-2。注意dp要初始化为-inf。思路确实巧妙。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int N = 2020; 7 int a[N], inf = 1e8; 8 int dp[N]; 9 int main()10 {11 int t, n;12 scanf("%d", &t);13 while(t--) {14 scanf("%d", &n);15 for(int i = 1; i <= n - 1; ++i) {16 scanf("%d", a + i);17 dp[i] = -inf;18 }19 for(int i = 2; i <= n - 1; ++i) {20 for(int j = 1; j <= n - 2; ++j) {21 if(j >= i - 1) {22 dp[j] = max(dp[j], dp[j - i + 1] + a[i] - a[1]);23 }24 }25 }26 printf("%d\n", dp[n - 2] + n*a[1]);27 }28 return 0;29 }
HDU 5534 Partial Tree (完全背包变形)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。