HDU 5534/ 2015长春区域H.Partial Tree DP Partial Tree

HDU 5534/ 2015长春区域H.Partial Tree DP
Partial Tree

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

nodes but lacks of

edges. You want to complete this tree by adding

edges. There must be exactly one path between any two nodes after adding. As you know, there are

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

, where

is a predefined function and

is the degree of this node. What's the maximum coolness of the completed tree?

Input

The first line contains an integer

indicating the total number of test cases.
Each test case starts with an integer

in one line,
then one line with

integers

There are at most

test cases with

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个点，给你1到n-1的度数的价值，让你构造一棵树这颗树的价值就是，度数代表的价值和，问最大是多少，

题解：首先度的总和为2(n-1)，并且每个节点度不为0。如果用二维dp[i][j]表示第i个节点还剩j个度的最优值，是没问题，但是复杂度为

。但是其实每个节点都要分配一个度，那么我们先给每个节点分配一个度，剩下n-2的度分给n个点，可以减掉一维，dp[i]表示i个度的最优值，因为度的个数是严格小于节点个数的。背包转移的权值为val[i]-val[1]（可能有负数）

#include<cstdio>
using namespace std ;
#define inf 1000000
int main(){
  int dp[2016],a,b,n,i,T,j;
   scanf("%d",&T);
     while(T--){
        scanf("%d%d",&n,&a);
        for( i=1;i<n;i++){dp[i]=-inf;}
        for( i=2;i<n;i++){
                scanf("%d",&b);b=b-a;
            for( j=i-1;j<=n-2;j++){
                if(dp[j-(i-1)]+b>dp[j])
                dp[j]=dp[j-(i-1)]+b;
            }
        }
       printf("%d
",n*a+dp[n-2]);
     }
  return 0;
}

代码

HDU 5534/ 2015长春区域H.Partial Tree DP Partial Tree

相关推荐