hdu 5534 Partial Tree(完全背包)

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two nodes are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

You find a partial tree on the way home. This tree has nn nodes but lacks of n−1n−1edges. You want to complete this tree by adding n−1n−1 edges. There must be exactly one path between any two nodes after adding. As you know, there are nn−2nn−2 ways to complete this tree, and you want to make the completed tree as cool as possible. The coolness of a tree is the sum of coolness of its nodes. The coolness of a node is f(d)f(d), where ff is a predefined function and dd is the degree of this node. What's the maximum coolness of the completed tree?

Input

The first line contains an integer TT indicating the total number of test cases.
Each test case starts with an integer nn in one line,
then one line with n−1n−1 integers f(1),f(2),…,f(n−1)f(1),f(2),…,f(n−1).

1≤T≤20151≤T≤2015
2≤n≤20152≤n≤2015
0≤f(i)≤100000≤f(i)≤10000
There are at most 1010 test cases with n>100n>100.

Output

For each test case, please output the maximum coolness of the completed tree in one line.

Sample Input

Sample Output

5
19

就是说有n个物品，每个物品体积分别是1,2,3...n 背包容量为2（n-1）又给出它们的价值

求背包中恰好用到n个物品，恰好将背包装满能够得到的最大价值。

一开始dp[物品数量][背包体积 ] n3复杂度 T了

查阅博客后提前给n个物品都给一个 a[1] 就不用考虑所用物品数量了

注意到一个节点数为n的树的度数和为2*n-2,所以问题就转换为了把2*n-2个度分配给n个节点所能获得的最大价值，而且每一个节点至少分到1个度。我们可以先每一个分一个度，然后把n-2个节点任意分配完。分配的时候因为已经分了1个度了，所以要把2~n-1的度看为1~n-1，然后做个完全背包就行了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
       int a[2030],dp[2030],n;
       scanf("%d",&n);
       for(int i=1;i<n;i++)
       {
           scanf("%d",&a[i]);
       }
       for(int i=2;i<n;i++)
       {
           a[i]=a[i]-a[1];
       }
       for(int i=0;i<2030;i++)
       {
        dp[i]=-1000000;
       }
       dp[0]=0;
       int ans=0;
       ans+=a[1]*n;
       for(int j=2;j<=n-1;j++)
       {
           for(int i=1;i<=n-2;i++)
           {
               if(i+1>=j)
               dp[i]=max(dp[i],dp[i-j+1]+a[j]);
           }
       }
       printf("%d\n",ans+dp[n-2]);
   }
    return 0;
}