HDU 5534 Partial Tree 完全背包

时间：2023-03-09 16:48:10
HDU 5534 Partial Tree 完全背包

一棵树一共有2*（n-1)度，现在的任务就是将这些度分配到n个节点，使这n个节点的权值和最大。

思路：因为这是一棵树，所以每个节点的度数都是大于1的，所以事先给每个节点分配一度，答案 ans=f[1]*n

先将答案赋值

所以接下来研究的就是，将剩下的n-2个度分配

即分别看 分配度数为1到n-2的节点的有几个（因为每个节点已经有一度），然后因为每个节点都加上了权值f[1],所以这时f[2]=f[2]-f[1]，以此类推，

看到这里，就是一个完全背包问题：如果还没看出来，详细一点

有1到n-2这些物品，每种物品都有无限个，权值是f[i],现在有一个容量为n-2的背包，去放这些物品，最后使价值最大（就是一个裸的背包问题）

大概就是这样，语言表达能力有限

/*

Problem : 5534 ( Partial Tree )     Judge Status : Accepted

RunId : 15511658    Language : G++    Author : qianbi08

*/

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include <algorithm>

#include<cstring>

using namespace std;

const int INF=-0x3f3f3f3f;

const int maxn=;

int dp[maxn],f[maxn];

int main()

{

   int T,n,ans;

   scanf("%d",&T);

   while(T--)

   {

       scanf("%d",&n);

       for(int i=;i<n;++i)

        scanf("%d",&f[i]);

       memset(dp,INF,sizeof(dp));

       ans=n*f[];

       dp[]=;

       for(int i=;i<n;++i)

        f[i]-=f[];

       for(int i=;i<n-;++i)

        f[i]=f[i+];

       for(int i=;i<=n-;++i)

        for(int j=i;j<=n-;++j)

          dp[j]=max(dp[j],dp[j-i]+f[i]);

       printf("%d\n",ans+dp[n-]);

   }

    return ;

}

相关文章