2015长春 HDU 5534 Partial Tree
阅读原文时间:2024年06月28日阅读:1

题意:有n个结点,n-1条边,现在要把这n个结点连成一棵树,给定了f(i),表示度为i的结点的价值是f(i)。现在问如何连能够使得Σf(i)的值最大。

思路:每个点至少一个度,所以可分配的度数为n-2,那么剩下就是每种物品可以任意选,转化成背包问题。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define clc(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=;
const int maxnode=;
const int inf=0x3f3f3f3f;
typedef long long LL;

int main()
{
int t,n;
int f[],dp[];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%d",&f[i]);
}
clc(dp,);
dp[]=n*f[];
for(int i=;i<=n-;i++)
{
for(int j=i;j<=n-;j++)
{
dp[j]=max(dp[j],dp[j-i]+f[i+]-f[]);//容量为j的背包增加i度后的价值
}
}
printf("%d\n",dp[n-]);
}
return ;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章