Partial Tree
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5534
完全背包
做这题前去学习了下完全背包，觉得这个优化简直神技！（以前都是用01背包做的，数据水的话可以过= =）
for(int i=;i<=n;++i)
for(int j=i;j<=V;++j)
dp[j]=max(dp[j],dp[j-i]+v[i]);
完全背包 时间复杂度O（VE）
我们回到这道题，显然整棵树的总的度为2n-2，相当于将2n-2个度分配到n个结点中去；
为了保证没有一个结点的度为0，现将每个结点的度预设为1；
于是问题就相当于往容量为n-2的背包中放东西，东西的代价度，权值为f（x），也就是完全背包的变形了。
设状态：dp[j]表示度为i时的最大值
状态转移方程：dp[j]=max(dp[j],dp[j-i]+f[i+1]-f[1])
代码如下：
#include<cstdio>
#include<cstring>
#define Max(x,y) (x>y?x:y)
#define N 2020
using namespace std;
typedef long long LL;
const LL INF=(LL)1e15;
LL T,n,dp[*N],f[N],lmt,ans;//dp[i]为存放i代价的最大价值
int main(void){
scanf("%I64d",&T);
while(T--){
scanf("%I64d",&n);
lmt=n-;
for(LL i=;i<=lmt;++i)
dp[i]=-INF;
for(LL i=;i<n;++i)
scanf("%I64d",&f[i]);
for(LL i=;i<n-;++i)
for(LL j=i;j<=lmt;++j)
dp[j]=Max(dp[j],dp[j-i]+f[i+]-f[]);
ans=dp[lmt]+n*f[];
printf("%I64d\n",ans);
}
}