H - Partial Tree HDU - 5534 【 完全背包 】

Partial Tree

H - Partial Tree

HDU - 5534 

Problem Description

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 n nodes but lacks of n−1 edges. You want to complete this tree by adding n−1 edges. There must be exactly one path between any two nodes after adding. As you know, there are nn−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), where f is a predefined function and d is the degree of this node. What's the maximum coolness of the completed tree?

Input

The first line contains an integer T indicating the total number of test cases. Each test case starts with an integer n in one line, then one line with n−1 integers f(1),f(2),…,f(n−1). 1≤T≤2015 2≤n≤2015 0≤f(i)≤10000 There are at most 10 test cases with n>100.

Output

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

Sample Input

2 3 2 1 4 5 1 4

Sample Output

5 19

&：把总的度看成是体积，对于 n 个点连成一个 n - 1 时，总的度是 2 * n - 2，因为必须要把所有点都连在一起，所以就可以先假设每个点都有一个度（最小），那样背包的体积就剩余了 n - 2 个了。然后按照完全背包跑就可以了，外层 for 是每个体积对应的贡献度，内层是体积的大小，状态转移方程 dp[ j ] = max( dp[ j ] ，dp[ j - i ] + val[ i + 1 ] - val[ 1 ] )；意思是体积 j 的包里可以有两种选择，不拿当前体积为 i 的东西， 那么还是 dp[ j ]，如果拿得话，就是体积要减掉 i，得到的贡献值是 val[ i + 1] ，因为相当于是抛弃了原来的那个体积为 1 的物品，这也就是最后面那个地方要减去 val[ 1 ]， 那么初始化 dp[ 0 ] = n * val[ 1 ]。

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 4e4 + 100;
int val[maxn];
int dp[maxn];
int main()
{
    int t,n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i < n; i ++)
        {
            scanf("%d", &val[i]);
        }
        memset(dp,0,sizeof(dp));
        dp[0] = n * val[1];
        for(int i = 1; i < n - 1; i ++)
        {
            for(int j = i; j <= n - 2; j ++)
            {
                dp[j] = max(dp[j],dp[j - i] + val[i + 1] - val[1]);
            }
        }
        printf("%d\n",dp[n - 2]);
    }
    return 0;
}