D-牛牛种小树_牛客练习赛89 (nowcoder.com)
题目描述
数据范围
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; }
