题解：P12734 理解

考虑所有的操作，一定覆盖了这个森林中的若干子连通块，显然每个子连通块也可以看作一棵有根树。

由于这些子连通块的操作互不影响（因为可以把其他连通块的全部忘掉再操作），我们可以单独考虑。

考虑计算以

u

为根的某个连通块至少需要的记忆容量，设

u

的儿子为

v

，

定义以

u

为根的连通块

k

合法，当且仅当能从

u

回忆，通过不断联想和删除的方式遍历这整个连通块，且最大的记忆数 不超过

k(k\ge 2)

，

如果 $u$ 的儿子数量 $=1$ ，且 $v$ 是 $k$ 合法，那么 $u$ 也是 $k$ 合法。
如果 $u$ 的儿子数量 $>1$ ，且所有儿子都是 $k$ 合法，那么 $u$ 是 $k+1$ 合法。
如果 $u$ 恰好有一个儿子是 $k+1$ 合法，其他儿子都是 $k$ 合法，那么 $u$ 是 $k+1$ 合法。

当且仅当连通块大小恰好为

1

时，才能做到

k=1

合法，这一点需要特殊转移。

有了这个我们就可以树形DP 求解了，设

f(u,i)

表示已经遍历完

u

的子树的所有关键点，以

u

为根的连通块

i

合法的最小代价。

转移是容易的，情况

1

和情况

3

可以合并。

CPP

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 1e5 + 5, K = 15;
const LL INF = 2e18;

int n, m, k, p[N], q[N];
LL a[N], b[N];

namespace Task3 {
    vector<int> G[N];
    LL f[N][K];
    bool vis[N];
    
    void dfs(int u) {
        for (int v : G[u]) dfs(v);

        if (vis[u]) f[u][0] = INF;
        else {
            f[u][0] = 0;
            for (int v : G[u]) f[u][0] += min(f[v][0], f[v][k]);
        }

        f[u][1] = a[u];
        for (int v : G[u]) f[u][1] += min(f[v][0], f[v][k]);

        int cnt = G[u].size();
        vector<LL> pre(cnt + 10, 0), suf(cnt + 10, 0);
        for (int i = 2; i <= k; i++) {
            for (int j = 0; j < cnt; j++) {
                int v = G[u][j];
                pre[j] = min({f[v][0], f[v][k], f[v][i - 1] - a[v] + b[v]});
                if (j) pre[j] += pre[j - 1];
            }
            suf[cnt] = 0;
            for (int j = cnt - 1; j >= 0; j--) {
                int v = G[u][j];
                suf[j] = suf[j + 1] + min({f[v][0], f[v][k], f[v][i - 1] - a[v] + b[v]});
            }
            if (cnt /* Notice! */) f[u][i] = pre[cnt - 1];
            for (int j = 0; j < cnt; j++) {
                int v = G[u][j];
                if (j) f[u][i] = min(f[u][i], f[v][i] - a[v] + b[v] + pre[j - 1] + suf[j + 1]);
                else f[u][i] = min(f[u][i], f[v][i] - a[v] + b[v] + suf[j + 1]);
            }
            f[u][i] += a[u];
        }
        
        for (int i = 2; i <= k; i++) f[u][i] = min(f[u][i], f[u][i - 1]);
    }

    void solve() {
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= m; i++) vis[q[i]] = true;
        for (int i = 1; i <= n; i++) {
            if (p[i]) G[p[i]].push_back(i);
        }
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!p[i]) {
                dfs(i);
                ans += min(f[i][0], f[i][k]);
            }
        }
        cout << ans << '\n';
        for (int i = 1; i <= n; i++) G[i].clear();
    }
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= m; i++) cin >> q[i];

    sort(q + 1, q + 1 + m);
    m = unique(q + 1, q + 1 + m) - (q + 1);

    if (k == 1) {
        LL sum = 0;
        for (int i = 1; i <= m; i++) sum += a[q[i]];
        cout << sum << '\n';
        return;
    }

    Task3::solve();
}

文章操作

相关推荐

评论

题解：P12734 理解