D-牛牛种小树_牛客练习赛89(完全背包)

简介: 笔记

D-牛牛种小树_牛客练习赛89 (nowcoder.com)


题目描述

200.png

数据范围

1 < n ⩽ 1 e 4 , 1 ⩽ f ( i ) ⩽ 1 e 9


思路

首先我们可以将所有点看成连有一条边的孤立的点,其度为1.我们又知道 一棵树的度之和为2∗n−2 所以还未分配的度数为n−2 。


那么接下来对度数进行完全背包,背包的容量即为还未分配的度数 n−2


第一重循环枚举度数 i ,第二重枚举背包容量,第三重循环枚举能将多少个节点置成当前的度数 i。


因为点数为 n 的树中,一个节点的最大度数为n−1,且每个点已经分配了一个度 所以 i从 2枚举到n−1。


朴素的dp过程如下:


dp[i][j] 表示已经求出了将若干度为 1的点的度数置成2 ~ i − 1中的一个且消耗了 j个自由的度得到的最大值。

for(int i = 2; i < n;++i){ // 度数
    for(int j = 0;j <= n - 2;++j){ // 背包容量
        for(int k = 0; k * i <= j;++k){ // 将 k 个点的度数置为 i
            // 之所以 + f[i] - f[1] 是因为将当前点的度数变为 i 可以得到 f[i]的贡献
            // 但是之前这个点的度数为 1,所以要减去 f[1]
            dp[i][j] = max(dp[i][j],dp[i - 1][j - (k * i)] + f[i] - f[1]);
        }
    }
}


答案为dp[n−1][n−2]


根据完全背包的优化原理,可以得到下面的代码:


代码

#include<bits/stdc++.h>
#include<unordered_map>
#define int long long
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define MOD 998244353
#define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i))
#define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i))
#define debug(x) cerr << " == " << (x) << endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T> inline T lowbit(T x) { return x & -x; }
//template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; }
const int N = 1e5 + 10;
int n;
int dp[N];
int f[N];
void solve() {
  cin >> n;
  for (int i = 1; i < n; ++i) {
    cin >> f[i];
  }
  dp[0] = 1ll * n * f[1];
  for (int i = 2; i <= n; ++i) {
    for (int j = i - 1; j <= n - 2; ++j) {
      dp[j] = max(dp[j], dp[j - (i - 1)] + f[i] - f[1]);
    }
  }
  cout << dp[n - 2ll] << endl;
}
signed main() {
  // int _; cin >> _;
  // while (_--)
    solve();
  return 0;
}





目录
打赏
0
0
0
0
1
分享
相关文章
牛客练习赛87 牛老板 (记忆化搜索)
牛客练习赛87 牛老板 (记忆化搜索)
138 0
2017"百度之星"程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】
度度熊保护村庄 Accepts: 13 Submissions: 488 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 哗啦啦村袭击了喵哈哈村! 度度熊为了拯救喵哈哈村,带着自己的伙伴去救援喵哈哈村去了!度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地,牢牢的守住了喵哈哈村。
1645 0
牛客-xinjun与阴阳师(分组背包)
牛客-xinjun与阴阳师(分组背包)
112 0
【蓝桥杯集训·每日一题】AcWing 3305. 作物杂交
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 Spfa算法
134 0
【力扣】爬楼梯问题 小时候家长考过你吗?
【力扣】爬楼梯问题 小时候家长考过你吗?
128 0
【力扣】爬楼梯问题 小时候家长考过你吗?
【AcWing周赛】AcWing第86场周赛
目录 <一>AcWing 4794. 健身 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 <二>AcWing 4795. 安全区域 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 <三>AcWing 4796. 删除序列 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
90 0
【AcWing周赛】AcWing第85场周赛
目录 &lt;一&gt;Acwing 4791. 死或生 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 &lt;二&gt;Acwing 4792. 最大价值 一、题目 1、原题链接 2、题目描述 二、解题报告: 1、思路分析 2、时间复杂度 3、代码详解 &lt;三&gt;Acwing 4793. 危险程度 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 &lt;四&gt; 知识风暴 1、排序不等式 2、贪心法 3、数据范围 4、并查集 基本操作
87 0
【AcWing每日一题】4818. 奶牛大学
【AcWing每日一题】4818. 奶牛大学
134 0
牛客网——牛牛的通勤
牛客网——牛牛的通勤
202 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等