[ICPC2020南京M] Monster Hunter

[ICPC2020南京M] Monster Hunter - 树形dp,背包dp

Description

给定一颗大小为 (n) 的有根树，每个结点都有点权 (hp[i])，选取点的代价是 (hp[i] + sum_{son of i} hp[j])，且其父亲也被选 现在可以在这棵树中删除 (0-n) 个点，问删除这些点的情况下最小的代价分别是多少

Solution

设 (f[p][v][0/1]) 表示 (p) 子树内，枪毙 (v) 个点，是否枪毙 (p) 时的总代价

转移枚举的时候注意顺序，否则会复杂度会退化到立方

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

#define int long long

const int N = 2005;

int n, a[N];
vector<int> g[N];
int siz[N], f[N][N][2], h[N][2];

void dfs(int p)
{
    siz[p] = 1;
    f[p][0][0] = a[p];
    f[p][1][1] = 0;
    int cnt = 1;
    random_shuffle(g[p].begin(), g[p].end());
    for (int q : g[p])
    {
        dfs(q);
        siz[p] += siz[q];
        for (int i = siz[p]; i >= 0; i--)
            h[i][0] = h[i][1] = 1e18;
        for (int t = cnt; t >= 0; t--)
        {
            for (int j = 0; j <= siz[q]; j++)
            {
                int i = t + j;
                h[i][0] = min(h[i][0], min(f[q][j][0] + a[q] + f[p][i - j][0], f[q][j][1] + f[p][i - j][0]));
                h[i][1] = min(h[i][1], min(f[q][j][0] + f[p][i - j][1], f[q][j][1] + f[p][i - j][1]));
            }
        }
        cnt += siz[q];
        for (int i = cnt; i >= 0; i--)
            f[p][i][0] = h[i][0], f[p][i][1] = h[i][1];
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        g[i].clear(), siz[i] = 0;
    for (int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k < 2; k++)
                f[i][j][k] = 1e18;
    dfs(1);
    for (int i = 0; i <= n; i++)
        cout << min(f[1][i][0], f[1][i][1]) << " ";
    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}