ACM模版

描述

题解

好恶心的一个翻译题，翻译了半天不知道嘛子意思……

最后总算是搞懂了，大致说一下，题目要求我们构造一颗包含 n 个结点的树，树的价值为 ∑ni=1f(deg(i)) ，其中 deg(i) 表示结点 i 的度， f(x) 表示度为 x 的结点的价值。

所以很明显，一共有 n−1 条边， 2∗(n−1) 度，并且每个结点最低为一度，所以首先我们需要给每个结点分一度，剩下 n−2 度，也就是说要将这 n−2 分配给 n 个结点，并且每个结点度不限，那么结点度数最多为 n−1 ，所以很明显这就是一个完全背包问题。

那么问题来了，我们如何给每个结点分一度，后续又不产生冲突呢？自然是先给答案加上 f(1)∗n ，表示每个结点分配一度，然后对 f(2)、…、f(n−1) 统统减去 f(1) ，这样当增加其他的度数的结点时，并不需要再减去一开始分配的这一度所构成的价值。不过，在完全背包过程中，注意虽然一开始分配的度构成的价值不会多算，但是度数还是要减去的，所以也就是代码中为什么 i+j−1 的原因。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 2e4 + 5;
const int INF = 0x3f3f3f3f;

int n;
int a[MAXN];
int dp[MAXN];

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i < n; i++)
        {
            scanf("%d", a + i);
        }

        for (int i = 0; i <= n; i++)
        {
            dp[i] = -INF;
        }

        for (int i = 2; i < n; i++)
        {
            a[i] -= a[1];
        }

        dp[0] = 0;
        for (int i = 2; i < n; i++)
        {
            for (int j = 0, t = n - 1; i + j - 1 < t; j++)
            {
                dp[i + j - 1] = max(dp[i + j - 1], dp[j] + a[i]);
            }
        }

        printf("%d\n", a[1] * n + dp[n - 2]);
    }

    return 0;
}