首页 > 代码库 > hdu 5534 (完全背包) Partial Tree

hdu 5534 (完全背包) 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 n nodes but lacks of n1 edges. You want to complete this tree by adding n1 edges. There must be exactly one path between any two nodes after adding. As you know, there are nn2 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 n1 integers f(1),f(2),,f(n1).

1T2015
2n2015
0f(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
232 145 1 4
 

 

Sample Output
519
 
首先,这个最终答案是与点的度有关,由于是个树,可以知道最后所有点的度数和是n*2-2,还有,每个点至少得有一个度,所以最终答案得先加上f[1]*n,然后现在
还剩下n-2个度,需要在n个点里分配,使得分配之后的权值最大,但是这个分配由于是有关联的,一个点的度数加了1之后必须得有另一个点的度数也加1,所以我们的
分配方案还得满足这个条件,不能随意分配,但是通过随意取几个n值构造一下树发现,n-2个度任意分给n个点的方案能够满足构造出一棵树,而且这个构造还挺有
规律,有递推性,所以大胆认为可以任意分配,好,现在n-2个度分配给n个点,每次可以分配1到n-1个度,问怎么分配值f()最大,这不就是一个背包么,还是一个完全
背包。再注意一下这是在每个点已经有了一个度的前提下,所以得减去f[1]。
 
 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6  7 #define inf 0x3f3f3f3f 8 const int M  = 1e4 + 10; 9 int dp[M],a[M];10 11 int max(int x,int y){return x>y?x:y;}12 13 int main()14 {15     int t,n;16     scanf("%d",&t);17     while (t--){18        scanf("%d",&n);19        for (int i=1 ; i<n ; i++) {20            scanf("%d",&a[i]);21            if (i!=1) a[i]-=a[1];22        }23        //int pa=n*2-2;24        for (int i=0 ; i<=n ; i++) dp[i]=-inf;25        dp[0]=0;//dp[1]=a[1];26        for (int i=2 ; i<n ; i++) {27            for (int j=0 ; j+i-1<=n-2 ; j++)28               dp[i+j-1] = max(dp[i+j-1],dp[j]+a[i]);29        }30        printf("%d\n",dp[n-2]+n*a[1]);31     }32     return 0;33 }

 

 

hdu 5534 (完全背包) Partial Tree