HDU 5534 Partial Tree（動態(tài)規(guī)劃）

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5534

題面：

Partial Tree Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 763????Accepted Submission(s): 374


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亞洲區(qū)長春站-重現賽（感謝東北師大） ?

題意：

??? 給定一顆無向樹的節(jié)點數和各個度對應的權值，定義酷度為每個節(jié)點的度數乘以相應的度對應的權值的總和，求最大酷度。

解題：

??? 比較直接的想法是dp[i][j]，表示前i個節(jié)點分配了j點度數能獲取的最大值，寫法清晰明了，可惜復雜度為n^3，明顯超時。

??? 結合樹的特殊結構，每個節(jié)點的度數最少為1，因此預先給每個節(jié)點分配一點度數，隨后再將剩余的2*(n-1)-n點度數分配，使之得到最大的酷度。

??? 狀態(tài)轉移方程可以改進為dp[i]，代表在原來均分了n點度數的基礎上，再分配i點度數所能獲取的最大酷度。因為已經保障了每個節(jié)點至少為1度，后續(xù)分配也不會出現多次替換的情況，因此省卻了位置這一維，復雜度降為n^2.問題得解。

??? dp[i]=max(dp[i],dp[i-j]+f[j+1]-f[1])；

代碼：

#include
#include
#include
#include
#include 
using namespace std;
int f[2020],dp[2020];
int main()
{
	int t,n,lim;
	scanf("%d",&t);
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);
		for(int i=1;i