题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534
题意：有n个节点，让这n个节点形成一棵树，这棵树的种类有很多种，现在告诉n-1个f[i]，表示度为 i 的点的权值为f[i]，求我们形成的那棵树的所有节点的权值和最大值；
n个节点形成的树的度数和为2*n-2，由于是一棵树，所以每个点一定有一个度，我们先把结果加上n*f[1] ,
那么还剩下n-2个度，通过举例不难发现，无论这n-2个度怎么分给n个点，都能构造出一棵树；
接下来我们就相当于是有编号为2到n-1的物品(共n-2个)（分配的时候因为已经分了1个度了，所以要把2~n-1的度看为1~n-2），每个物品的价值为f[i]-f[1];
每个物品的体积为i（编号）, 现有背包的体积大小为n-2，求把背包装满的最大价值;
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
#define met(a, b) memset(a, b, sizeof(a))
#define N 2105
#define INF 0x3f3f3f3f
typedef long long LL; int v[N], dp[N]; int main()
{
int T, n;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=; i<n; i++)
{
scanf("%d", &v[i]);
if(i != ) v[i] = v[i] - v[];
}
int ans = n*v[]; for(int i=; i<n; i++)
{
v[i] = v[i+];
dp[i] = -INF;
}
dp[] = ; for(int i=; i<n-; i++)
{
for(int j=i; j<=n-; j++)
dp[j] = max(dp[j], dp[j-i]+v[i]);
}
printf("%d\n", dp[n-]+ans);
}
return ;
}