牛牛种小树

题目链接：nowcoder 225544

到主站看：https://blog.csdn.net/weixin_43346722/article/details/120517394

题目大意

要你构造一个 n 个节点的数，然后给出你 f(i)，要你最大化 ∑i=1~n f(d[i])。
其中 d[i] 为 i 点的度数。

思路

我们考虑转换一下题意。

由于一个树的边数是 ，那所有点的度数之和就是 。

那就相当于我们要用 个数凑出 ，而且这些数都要在 之间。

那不难看出这是个完全背包，但是它规定了数选的个数一定要是 啊。

那我们考虑用这么一个方法，就是在背包的过程中保证它的个数不变。
我们考虑一开始是链的形式，那就是 个度数为 的， 个度数为 的。

然后我们背包设 为当前最大的度数是 ，还有 个度数为 的。
然后你每次要构度数 ，你就拿 个度数为二的点，把 个点的其中一个度数全部分配到一个点上，这样就多了 个度数为 的点， 个度数为 的点，少了 个度数为 的点，计算一下贡献的改变就好了。

然后由于普通的完全背包是 不能过，我们这里用到的是单调队列优化背包。
然后复杂度就变成 ，是能过的。

代码

#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

int n, bst, tmp;
ll a[10001], f[2][10001], ans;//f 滚动了

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

    f[2 & 1][n - 2] = 2ll * a[1] + 1ll * (n - 2) * a[2];//初始状态时链
    for (int i = 3; i < n; i++) {//新加入的度数
        for (int j = n - 2; (n - 2) - j < i - 1; j--) {//多重背包
            f[i & 1][j] = f[(i ^ 1) & 1][j];
            for (int k = j - (i - 1); k >= 0; k -= (i - 1)) {//枚举现在有多少个度数为 2 的
                f[i & 1][k] = max(f[(i ^ 1) & 1][k], f[i & 1][k + (i - 1)] + a[i] - (i - 1) * a[2] + (i - 2) * a[1]);
            }
        }
    }

    for (int i = 0; i <= n - 2; i++)//最后剩多少个 2 都可以
        ans = max(ans, f[(n ^ 1) & 1][i]);
    printf("%lld", ans);

    return 0;
}