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
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?
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.
- 给出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-2955-Robberies（0-1背包） 2020-03-30
- hdu1455 拼木棍（经典dfs） 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
