hdu5534 Partial Tree dp(难)
Partial Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 374 Accepted Submission(s): 209
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个度数分给n个点，剩下的就可以随便分了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define REP(i,a,b) for(int i=a;i<=b;i++) #define MS0(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int maxn=100100; const int INF=(1<<29); int f[maxn],n; ll dp[maxn]; int main() { int T;cin>>T; while(T--){ cin>>n; REP(i,1,n-1) scanf("%d",&f[i]); ll ans=f[1]*n; MS0(dp); REP(i,0,n-2) dp[i]=-INF; dp[0]=0; REP(i,1,n-2){ REP(j,0,i){ dp[i]=max(dp[i],dp[i-j]+f[j+1]-f[1]); //cout<<i<<" "<<dp[i]<<endl; } } ans+=dp[n-2]; printf("%I64d ",ans); } return 0; }
------可能是我小学生般的dp水平才觉得难，一定要狂补dp！