Partial Tree

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

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?

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.

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亚洲区长春站-重现赛（感谢东北师大）

题意：一个树的权值被定义为sigma(f(di), 1<=i<=n)其中di是第i个点的度数，求一个n个点的数的最大权值

分析：先把每个点的度数当成1，然后问题转化为总度数为2n-2，现有度数n，求增加n-2度数的最大权值

dp[i]表示增加i度数的最大权值

dp[i] = max(f[i+1], dp[j]+dp[i-j]), 1<=j<=i/2

完了

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <ctime>

 #include <iostream>

 #include <map>

 #include <set>

 #include <algorithm>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 using namespace std;

 typedef long long LL;

 typedef double DB;

 #define MIT (2147483647)

 #define MLL (1000000000000000001LL)

 #define INF (1000000001)

 #define For(i, s, t) for(int i = (s); i <= (t); i ++)

 #define Ford(i, s, t) for(int i = (s); i >= (t); i --)

 #define Rep(i, n) for(int i = (0); i < (n); i ++)

 #define Repn(i, n) for(int i = (n)-1; i >= (0); i --)

 #define mk make_pair

 #define ft first

 #define sd second

 #define puf push_front

 #define pub push_back

 #define pof pop_front

 #define pob pop_back

 #define sz(x) ((int) (x).size())

 #define clr(x, y) (memset(x, y, sizeof(x)))

 inline void SetIO(string Name)

 {

     string Input = Name + ".in";

     string Output = Name + ".out";

     freopen(Input.c_str(), "r", stdin);

     freopen(Output.c_str(), "w", stdout);

 }

 inline int Getint()

 {

     char ch = ' ';

     int Ret = ;

     bool Flag = ;

     while(!(ch >= '' && ch <= ''))

     {

         if(ch == '-') Flag ^= ;

         ch = getchar();

     }

     while(ch >= '' && ch <= '')

     {

         Ret = Ret *  + ch - '';

         ch = getchar();

     }

     return Ret;

 }

 const int N = ;

 int n, F[N];

 int Dp[N];

 inline void Solve();

 inline void Input()

 {

     int TestNumber = Getint();

     while(TestNumber--)

     {

         n = Getint();

         For(i, , n - ) F[i] = Getint();

         Solve();

     }

 }

 inline void Solve()

 {

     For(i, , n - ) F[i] -= F[];

     Dp[] = ;

     For(i, , n - )

     {

         Dp[i] = F[i + ];

         For(j, , (i / ) + )

             Dp[i] = max(Dp[i], Dp[j] + Dp[i - j]);

     }

     printf("%d\n", Dp[n - ] + n * F[]);

 }

 int main()

 {

     Input();

     //Solve();

     return ;

 }

巴特西

2015ACM/ICPC亚洲区长春站 H hdu 5534 Partial Tree

Partial Tree

最新文章

热门文章