首页 > 代码库 > Partial Tree---hdu5534（完全背包）
Partial Tree---hdu5534（完全背包）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534
题意：有n个节点，让这n个节点形成一棵树，这棵树的种类有很多种，现在告诉n-1个f[i]，表示度为 i 的点的权值为f[i]，求我们形成的那棵树的所有节点的权值和最大值；
n个节点形成的树的度数和为2*n-2，由于是一棵树，所以每个点一定有一个度，我们先把结果加上n*f[1] ,
那么还剩下n-2个度，通过举例不难发现，无论这n-2个度怎么分给n个点，都能构造出一棵树；
接下来我们就相当于是有编号为2到n-1的物品(共n-2个)（分配的时候因为已经分了1个度了，所以要把2~n-1的度看为1~n-2），每个物品的价值为f[i]-f[1];
每个物品的体积为i（编号）, 现有背包的体积大小为n-2，求把背包装满的最大价值;
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>#include<set>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define N 2105#define INF 0x3f3f3f3ftypedef long long LL;int v[N], dp[N];int main(){ int T, n; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<n; i++) { scanf("%d", &v[i]); if(i != 1) v[i] = v[i] - v[1]; } int ans = n*v[1]; for(int i=1; i<n; i++) { v[i] = v[i+1]; dp[i] = -INF; } dp[0] = 0; for(int i=1; i<n-1; i++) { for(int j=i; j<=n-2; j++) dp[j] = max(dp[j], dp[j-i]+v[i]); } printf("%d\n", dp[n-2]+ans); } return 0;}
Partial Tree---hdu5534（完全背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。