题意：有n个结点，n-1条边，现在要把这n个结点连成一棵树，给定了f(i)，表示度为i的结点的价值是f(i)。现在问如何连能够使得Σf(i)的值最大。
思路：每个点至少一个度，所以可分配的度数为n-2，那么剩下就是每种物品可以任意选，转化成背包问题。
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 }