HDU 5534 Partial Tree（動(dòng)態(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ū)長春站-重現(xiàn)賽（感謝東北師大） ?

題意：

??? 給定一顆無向樹的節(jié)點(diǎn)數(shù)和各個(gè)度對(duì)應(yīng)的權(quán)值，定義酷度為每個(gè)節(jié)點(diǎn)的度數(shù)乘以相應(yīng)的度對(duì)應(yīng)的權(quán)值的總和，求最大酷度。

解題：

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

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

??? 狀態(tài)轉(zhuǎn)移方程可以改進(jìn)為dp[i]，代表在原來均分了n點(diǎn)度數(shù)的基礎(chǔ)上，再分配i點(diǎn)度數(shù)所能獲取的最大酷度。因?yàn)橐呀?jīng)保障了每個(gè)節(jié)點(diǎn)至少為1度，后續(xù)分配也不會(huì)出現(xiàn)多次替換的情況，因此省卻了位置這一維，復(fù)雜度降為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