【HDOJ5534】Partial Tree（树，背包DP）

题意：有一棵n个点的形态不定的树，每个度为i的节点会使树的权值增加f[i]，求树的最大权值

n<=2015，0<=f[i]<=1e4

思路：对不起队友，我再强一点就能赛中出这题了

显然每个点的度至少为1，且度数为1的节点至少有2个（From 队友）

有一个结论：给每个点都分配1个度，剩余的度任意分配，一定能构造出对应的方案

仔细想想题面里的生成树数量不就在暗示我有类似Prufer序的性质么……序列与构造一一对应……唉太菜了

然后就是经典的完全背包问题了

每个点分配一个度之后还剩余n-2个度，每个点的分配到1之后多出来的度是[0,n-2]

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<ctime>

 #include<cmath>

 #include<algorithm>

 #include<iomanip>

 #include<vector>

 #include<map>

 #include<set>

 #include<bitset>

 #include<queue>

 #include<stack>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   2100

 #define M   110000

 #define eps 1e-8

 #define pi  acos(-1)

 #define oo  1000000000

 #define MOD 10007

 int a[N],f[N],dp[N];

 int main()

 {

     //freopen("hdoj5534.in","r",stdin);

     //freopen("hdoj5534.out","w",stdout);

     int cas;

     scanf("%d",&cas);

     for(int v=;v<=cas;v++)

     {

         int n;

         scanf("%d",&n);

         for(int i=;i<n;i++) scanf("%d",&a[i]);

         for(int i=;i<n;i++) f[i-]=a[i]-a[];

         int m=n-;

         memset(dp,,sizeof(dp));

         dp[]=n*a[];

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

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

         printf("%d\n",dp[m]);

     }

     return ;

 }

巴特西

【HDOJ5534】Partial Tree（树，背包DP）

最新文章

热门文章