2020ICPC南京 M.Monster Hunter

题目链接
题目描述
There is a rooted tree with $n$ vertices and the root vertex is $1$. In each vertex, there is a monster. The hit points of the monster in the $i$-th vertex is $h{p}_i$ .

Kotori would like to kill all the monsters. The monster in the $i$-th vertex could be killed if the monster in the direct parent of the $i$-th vertex has been killed. The power needed to kill the $i$-th monster is the sum of $h{p}_i$ and the hit points of all other living monsters who lives in a vertex $j$ whose direct parent is $i$. Formally, the power equals to

$$h{p}_i+\sum _{\begin{array}{c}\text{the monster in vertex }j\text{ is alive}\\ \text{and }i\text{ is the direct parent of }j\end{array}}h{p}_j$$
​

In addition, Kotori can use some magic spells. If she uses one magic spell, she can kill any monster using $0$ power without any restriction. That is, she can choose a monster even if the monster in the direct parent is alive.

For each $m=0,1,2,\cdots ,n$ , Kotori would like to know, respectively, the minimum total power needed to kill all the monsters if she can use mm magic spells.
输入描述:
There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ $(2\le n\le 2\times 10^3)$, indicating the number of vertices.

The second line contains $(n-1)$ integers $p_2,p_3,\cdots ,p_n$ $(1\le p_i<i)$ , where $p_i$ means the direct parent of vertex $i$.

The third line contains nn integers $h{p}_1,h{p}_2,\cdots ,h{p}_n$ $(1\le h{p}_i\le 10^9)$ indicating the hit points of each monster.

It’s guaranteed that the sum of nn of all test cases will not exceed $2\times 10^3$ .
输出描述:
For each test case output one line containing $(n+1)$ integers $a_0,a_1,\cdots ,a_n$ separated by a space, where $a_m$ indicates the minimum total power needed to kill all the monsters if Kotori can use $m$ magic spells.

Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!
示例1
输入

3
5
1 2 3 4
1 2 3 4 5
9
1 2 3 4 3 4 6 6
8 4 9 4 4 5 2 4 1
12
1 2 2 4 5 3 4 3 8 10 11
9 1 3 5 10 10 7 3 7 9 4 9

输出

29 16 9 4 1 0
74 47 35 25 15 11 7 3 1 0
145 115 93 73 55 42 32 22 14 8 4 1 0

E因为写分类讨论卡了近两个半小时，M题思路秒出，结果因为背包生疏到比赛结束都没有调过样例（虽然调出来也是T ）最终四题铜QAQ。。
首先，对于特定的咒语使用方案，power的总和也是确定的，因此考虑dp咒语使用方案。
设状态 $f[x][i][0/1]$ 表示以 $x$ 为根的子树使用 $i$ 个咒语且节点 $i$ 是/否被使用咒语时power和的最小值。
则状态转移方程为：
$$\{\begin{array}{cc}f[x][i][1]=& \min (\sum _{y_0,y_1\in so{n}_x\sum i_0+\sum i_1=i}f[y_0][i_0][0]+f[y_1][i_1][1]+hp[y_1])+hp[x]\\ f[x][i][0]=& \min (\sum _{y_0,y_1\in so{n}_x\sum i_0+\sum i_1=i-1}f[y_0][i_0][0]+f[y_1][i_1][1])\end{array}$$
注意同样的转移方程不同的写法转移次数是不同的，具体区别看下面两份代码。
TLE代码

#include<bits/stdc++.h>

using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 2e3 + 10;
const long long INF = 1e18;
int head[N], ver[N], Next[N], tot;
int T, n, siz[N], hp[N];
long long f[N][N][2], g[N][2];

inline void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

inline void init() {
    tot = 0;
    memset(head, 0, sizeof(int) * (n + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            f[i][j][0] = f[i][j][1] = 0;
}

void dp(int x) {
    siz[x] = 1;
    if (!head[x]) {
        f[x][0][0] = INF, f[x][0][1] = hp[x];
        f[x][1][0] = 0, f[x][1][1] = INF;
        return;
    }
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        dp(y), siz[x] += siz[y];
        for (int j = 0; j <= siz[x]; ++j)g[j][1] = g[j][0] = INF;
        for (int j = 0; j <= siz[x]; ++j)
            for (int k = 0; k <= min(j, siz[y]); ++k) {
                if (j < siz[x])g[j][1] = min(g[j][1], f[x][j - k][1] + min(f[y][k][0], f[y][k][1] + hp[y]));
                if (j > k)g[j][0] = min(g[j][0], f[x][j - k][0] + min(f[y][k][0], f[y][k][1]));
            }
        for (int j = 0; j <= siz[x]; ++j)f[x][j][1] = g[j][1];
        for (int j = 0; j <= siz[x]; ++j)f[x][j][0] = g[j][0];
    }
    for (int i = 0; i <= siz[x] - 1; ++i)f[x][i][1] += hp[x];
}

int main() {
    T = qr();
    while (T--) {
        n = qr(), init();
        for (int i = 2; i <= n; ++i)add(qr(), i);
        for (int i = 1; i <= n; ++i)hp[i] = qr();
        dp(1);
        for (int i = 0; i <= n; ++i)
            printf("%lld%c", min(f[1][i][0], f[1][i][1]), i == n ? 'n' : ' ');
    }
    return 0;
}

AC代码

#include<bits/stdc++.h>

using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

const int N = 2e3 + 10;
const long long INF = 1e18;
int head[N], ver[N], Next[N], tot;
int T, n, siz[N], hp[N];
long long f[N][N][2], g[N][2];

inline void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

inline void init() {
    tot = 0;
    memset(head, 0, sizeof(int) * (n + 1));
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            f[i][j][0] = f[i][j][1] = 0;
}


void dp(int x) {
    siz[x] = 1;
    if (!head[x]) {
        f[x][0][0] = INF, f[x][0][1] = hp[x];
        f[x][1][0] = 0, f[x][1][1] = INF;
        return;
    }
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        dp(y);
        for (int j = 0; j <= siz[x] + siz[y]; ++j)
            g[j][1] = g[j][0] = INF;
        for (int j = 0; j <= siz[x]; ++j)
            for (int k = 0; k <= siz[y]; ++k) {
                if (j + k < siz[x] + siz[y])
                    g[j + k][1] = min(g[j + k][1], f[x][j][1] + min(f[y][k][0], f[y][k][1] + hp[y]));
                if (j > 0)g[j + k][0] = min(g[j + k][0], f[x][j][0] + min(f[y][k][0], f[y][k][1]));
            }
        siz[x] += siz[y];
        for (int j = 0; j <= siz[x]; ++j)f[x][j][1] = g[j][1];
        for (int j = 0; j <= siz[x]; ++j)f[x][j][0] = g[j][0];
    }
    for (int i = 0; i <= siz[x] - 1; ++i)f[x][i][1] += hp[x];
}

int main() {
    T = qr();
    while (T--) {
        n = qr(), init();
        for (int i = 2; i <= n; ++i)add(qr(), i);
        for (int i = 1; i <= n; ++i)hp[i] = qr();
        dp(1);
        for (int i = 0; i <= n; ++i)
            printf("%lld%c", min(f[1][i][0], f[1][i][1]), i == n ? 'n' : ' ');
    }
    return 0;
}

最后

以上就是辛勤鸭子为你收集整理的2020ICPC南京 M.Monster Hunter的全部内容，希望文章能够帮你解决2020ICPC南京 M.Monster Hunter所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。