题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5534
题解：这题一看有点像树形dp但是树形dp显然没什么思路。然后由于这里的约束几乎没有就是一颗树然后是任意组合，但是有一点总的度数是2*n-2这是不变的，然后就是选择度数为1，2，3....n-1的点的组合，这么说说是不是有点像背包，然后可以想一下一开始所有点的度数都为1然后就是n*f[1]如果要组成一个度数为2的话只需要剪掉一个度数为1的也就是说f[1]然后加上f[2]即可，这样就很像一个背包
不妨设dp[i]表示度数为i最大为多少，dp[0]为n*f[1],dp[i]=max(dp[i],dp[i-j]+f[j+1]-f[1]),
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = + ;
int f[M] , dp[M];
int main() {
int t , n;
scanf("%d" , &t);
while(t--) {
scanf("%d" , &n);
for(int i = ; i < n ; i++) {
scanf("%d" , &f[i]);
}
memset(dp , , sizeof(dp));
dp[] = n * f[];
for(int i = ; i <= n - ; i++) {
for(int j = ; j <= i ; j++) {
dp[i] = max(dp[i] , dp[i - j] + f[j + ] - f[]);
}
}
printf("%d\n" , dp[n - ]);
}
return ;
}