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);

     }

 }

巴特西

Partial Tree

Partial Tree

最新文章

热门文章