HDU 5534-Partial Tree【完全背包+思维】

约定不等于承诺〃 2023-08-17 15:44 107阅读 0赞

题意：给你n个点，再给出来你f(1 ~ n) 就是每个度数的权值，让你构建一棵树，使得所有点的权值和最大。

思路：首先每个点的度数至少都是1，而且这n个点的度数总和必须是2n - 2， 因为这是一棵树。所以模型就转换成了

n - 1种类型的物品，第i个重量是i，价值是f(i)，挑选出n件物品，总重量是2n - 2的最大价值。

三维的很容易想到，但复杂度铁超，我们考虑二维来写。

首先每个点的度数至少为1，所以我们先令每个点的度数为1，我们还需要挑n - 2组，那就是完全背包模型了。

在考虑是否放入第j个物品时，如果放入度数就变成了f(j + 1) , 还需要减去原来的f(1) 。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 2e3 + 100;
    const int inf = 0x3f3f3f3f;
    int a[maxn];
    ll dp[maxn];
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            int n;
            scanf("%d", &n);
            for(int i = 1; i < n; ++i)
            {
                scanf("%d", &a[i]);
                if(i != 1)
                    a[i] -= a[1];
            }
            memset(dp, -0x3f, sizeof(dp));
            dp[0] =  0;
            for(int i = 1; i < n - 1; ++i)
                for(int j = i; j <= n - 2; ++j)
                    dp[j] = max(dp[j], dp[j - i] + a[i + 1]);
            ll ans = dp[n - 2] + 1ll * n * a[1];
            printf("%lld\n", ans);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，107人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 5534-Partial Tree【完全背包+思维】

题意：给你n个点，再给出来你f(1 ~ n) 就是每个度数的权值，让你构建一棵树，使得所有点的权值和最大。思路：首先每个点的度数至少都是1，而且这n个点的度数总和必须是2n

约定不等于承诺〃/ 2023年08月17日 15:44/ 0 赞/ 108 阅读

相关 HDU 1171(完全背包)

题意：给一个数n，接下来n行，每行对应一个设备的两个值，第一个为设备的价值，第二个为该设备的数量。如何把所有设备一分为二，求两部分的价值总和尽量接近。 incl

蔚落/ 2022年09月20日 11:23/ 0 赞/ 196 阅读

相关 HDU 1114（完全背包）

题意：给出小猪钱罐空时的重量E，满时的重量F，钱币的种类N，接下来N行，分别为p w，p为钱币价值，w为钱币重量，求钱罐中钱币的最小价值。 include <c

╰+攻爆jí腚メ/ 2022年09月20日 11:17/ 0 赞/ 198 阅读

相关 HDU 2159-FATE(完全背包)

FATE Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

客官°小女子只卖身不卖艺/ 2022年07月24日 06:14/ 0 赞/ 151 阅读

相关 hdu 1171 - Big Event in HDU(完全背包)

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=1171][http_acm.hdu.edu.cn_showproblem.p

待我称王封你为后i/ 2022年07月12日 08:12/ 0 赞/ 137 阅读

相关 hdu 1171 - Big Event in HDU(完全背包)

地址 [http://acm.hdu.edu.cn/showproblem.php?pid=1171][http_acm.hdu.edu.cn_showproblem.p

你的名字/ 2022年07月12日 08:12/ 0 赞/ 139 阅读

相关完全背包基础 HDU - 1114 

Before ACM can do anything, a budget must be prepared and the necessary financial sup

迈不过友情╰/ 2022年06月17日 09:39/ 0 赞/ 146 阅读

相关 01背包+完全背包 HDU - 5410 

Today is CRB's birthday. His mom decided to buy many presents for her lovely son. S

喜欢ヅ旅行/ 2022年06月17日 09:27/ 0 赞/ 209 阅读

相关 Piggy-Bank-HDU1114-完全背包

Piggy-Bank Problem Description Before ACM can do anything, a budget must be p

不念不忘少年蓝@/ 2022年06月05日 05:56/ 0 赞/ 163 阅读

相关【HDU 2159】FATE（完全背包）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2159][http_acm.hdu.edu.cn_showproblem.ph

落日映苍穹つ/ 2022年02月15日 07:53/ 0 赞/ 227 阅读