题目链接:LOJ 6395

经过选拔,Kiana 成为了可乐城的市长,为了兑现选举承诺,她决定在可乐城的 $n$ 个重要地标之间修建地铁。

可乐城的交通状况并不复杂,在任意两个地标之间修建一条地铁轨道都是可行的,但是地铁轨道并不是越多越好,如果有太多地铁从一个地标处经过,该地标的拥堵程度将大幅增加。为此,Kiana 决定给每个地标一个便利度来衡量拥堵程度,如果有 $d$ 条地铁轨道经过了某个地标,那么该地标的便利度为 $f(d) \bmod 59393$,其中 $f(x) = \sum_{i = 0} ^ {k} a_i x ^ i$ 是 Kiana 指定的一个 $k$ 次多项式。

因为修建地铁有一定的成本,所以 Kiana 希望新建的地铁轨道尽可能少,但任意两座地标之间都需要能通过地铁相互到达。Kiana 想知道在给定的条件下,什么样的修建方案可以使得地标的便利度之和最大。由于她不会做,所以希望你来告诉她答案。

数据范围:$1 \le n \le 3000$,$1 \le k \le 10$,$0 \le a_i \le 50$。


Solution

考虑 Prufer 序列,$f(i, j)$ 表示考虑了前 $i$ 个点,当前 Prufer 序列的长度为 $j$,那么有转移 $f(i, j) = \max \{ f(i - 1, j - k) + f(k + 1)\}$,预处理出所有 $f(x)$ 后 $\mathcal O(1)$ 转移。

最后根据 Prufer 序列还原出原树。

时间复杂度:$\mathcal O(n ^ 2)$。


Code

#include <bits/stdc++.h>

const int N = 3e3, K = 10, MOD = 59393;
int n, k, a[K + 5], f[N + 5], pre[N + 5], w[N + 5], deg[N + 5];

inline int calc(int x) {
    int ans = 0;
    for (int i = k; i >= 0; i--) {
        ans = (ans * x + a[i]) % MOD;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= k; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        w[i] = calc(i);
    }
    if (n == 1) {
        printf("0 %d\n", a[0]);
        return 0;
    }
    if (n == 2) {
        printf("1 %d\n1 2\n", w[1] * 2);
        return 0;
    }
    std::fill(f + 1, f + n - 1, INT_MIN);
    f[0] = w[1] * n;
    for (int i = 1; i <= n - 2; i++) {
        for (int j = 1; j <= i; j++) {
            if (f[i] < f[i - j] + w[j + 1] - w[1]) {
                f[i] = f[i - j] + w[j + 1] - w[1];
                pre[i] = j;
            }
        }
    }
    std::vector<int> prufer;
    for (int i = 1, k = n - 2; k > 0; i++) {
        for (int j = 1; j <= pre[k]; j++) {
            prufer.push_back(i);
        }
        deg[i] = pre[k];
        k -= pre[k];
    }
    printf("%d %d\n", n - 1, f[n - 2]);
    std::set<int> set;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            set.insert(i);
        }
    }
    for (auto u : prufer) {
        printf("%d %d\n", u, *set.begin());
        set.erase(set.begin());
        if (--deg[u] == 0) {
            set.insert(u);
        }
    }
    printf("%d %d\n", *set.begin(), *set.rbegin());
    return 0;
}
最后修改:2020 年 12 月 22 日 07 : 56 AM