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 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?
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?
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 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.
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.
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
- 给出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("%lldn",c[n-2]); 42 } 43 } 44 return 0; 45 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
