2015长春 HDU 5534 Partial Tree

时间:2022-11-08 18:54:44

题意:有n个结点,n-1条边,现在要把这n个结点连成一棵树,给定了f(i),表示度为i的结点的价值是f(i)。现在问如何连能够使得Σf(i)的值最大。

思路:每个点至少一个度,所以可分配的度数为n-2,那么剩下就是每种物品可以任意选,转化成背包问题。

2015长春 HDU 5534 Partial Tree2015长春 HDU 5534 Partial Tree
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <queue>
 8 #include <map>
 9 #include <vector>
10 #define clc(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 const int maxn=111;
13 const int maxnode=4000010;
14 const int inf=0x3f3f3f3f;
15 typedef long long LL;
16 
17 int main()
18 {
19     int t,n;
20     int f[2020],dp[2020];
21     scanf("%d",&t);
22     while(t--)
23     {
24         scanf("%d",&n);
25         for(int i=1; i<n; i++)
26         {
27             scanf("%d",&f[i]);
28         }
29         clc(dp,0);
30         dp[0]=n*f[1];
31         for(int i=1;i<=n-2;i++)
32         {
33             for(int j=i;j<=n-2;j++)
34             {
35                 dp[j]=max(dp[j],dp[j-i]+f[i+1]-f[1]);//容量为j的背包增加i度后的价值
36             }
37         }
38         printf("%d\n",dp[n-2]);
39     }
40     return 0;
41 }
View Code