首页 > > 程序设计 > C/C++ >

HDU_5534_Partial Tree

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

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

Input

The first line contains an integer

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 }