HDU_5534_Partial Tree

2018-06-17 21:48:29来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Partial Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1659    Accepted Submission(s): 818


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
2 3 2 1 4 5 1 4
 

 

Sample Output
5 19
 

 

Source
2015ACM/ICPC亚洲区长春站-重现赛(感谢东北师大)
 
  • 给出n个点让建树
  • 对于一个度为d的点有函数f(d)的对应数值,使得将所有节点度数对应函数数值加和最大
  • 显然不可能一个一个地建树
  • 对于二叉树来说对于节点数n,所有可建树的种类与卡特兰数有关,何况这题不限于二叉树
  • 测试n在比较小的时候几个例子,不难看出每次随着点数的扩增,都是从(n-1)的每种度数序列中将一个点度数增1,度数为1的点增1
  • 那么这里会引发出两种思路,一种是贪心,一种是递推,或者说是dp
  • 先说贪心的想法:
  • 每次节点数量增1的过程中,贪心地看当前度数序列中哪一个度数增1后节点度数对应函数值增量最大,然后总是挑增量最大的点来增加度数
  • 看似很有道理,但是有一个明显的反例,就是说f(n-1)数值远远超过其他数值,贪心的思路不能保证最后可以推到一个点有n-1个度的情况,因为每次贪的是当前的最大增量,在增加点的过程中很有可能对于函数f(d)会有卡在某一度数的情况,例如:a<b<c, f(a)<f(b), f(b)>f(c)。在这种情况下贪心策略可能会让尽可能多的点集中到度数b而计算不到度数在c以后的情况
  • 递推想法一:
  • 根据节点数递推,用dp[n]推出dp[n+1]
  • 看似正确,但是其思路其实和贪心策略一致
  • 但是更深层次的考虑的话会发现dp[n]和dp[n+1]没有一致的结构保障,意思是节点数n的结果和节点数n+1的建树结果不能保证除1点外完全相同
  • 而如果考虑用dp[1--n]推dp[n+1]也是一样,没有结构一致的保证,也没有保证第n+1棵数是由之前多少棵数组合而成,都是不确定的,没有保障的
  • 递推想法二:
  • 之前的两种思路都是在点的基础上引发的,我们现在考虑这个题中的重要变量,就是节点的度
  • 对于n和节点的树,有n-1个边,2n-2个度,每个节点至少1个度,一条边包含两边节点的2个度
  • 我们不妨把度看做半个边,两个度为1条边,对于度做dp
  • 这样做的好处在于同一度数序列对应不止一个树的结构,可以进行扩展
  • 初始化每个节点1个度,扩展次数为n-2次 
  • 每次从之前的情况递推,max更新dp[n+1]即可
  • dp[i]=max(dp[i],dp[j]+f[i-j+1]-f[1]);(j<i)
  • 其中减去的f[1]对应初始赋给每一个点的值,这里的意义在于对于前一种情况j,条一个度数为1的点进行扩展,将(i-j+1)个点组合在一起,形成一个菊花状(好吧,多校的题解里有类似的题,然后就用菊花来形容了),而且可以保证和原始树相连,就达成了扩展的操作

 

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int T, n;
25 LL f[maxn], c[maxn];
26 int main(){
27     // freopen("in.txt","r",stdin);
28     // freopen("out.txt","w",stdout);
29     while(~scanf("%d",&T)){
30         while(T--){
31             scanf("%d",&n);
32             for(int i=1;i<n;i++)
33                 scanf("%lld",&f[i]);
34             c[0]=n*f[1];
35             for(int i=1;i<=n-2;i++){
36                 c[i]=0LL;
37                 for(int j=0;j<i;j++){
38                     c[i]=max(c[i],c[j]+f[i-j+1]-f[1]);
39                 }
40             }
41             printf("%lld\n",c[n-2]);
42         }
43     }
44     return 0;
45 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU_5538_House Building

下一篇:【luogu 3382】【模板】三分法