2020ICPC 南京 Monster Hunter（树形依赖背包）

本文主要是介绍2020ICPC 南京 Monster Hunter（树形依赖背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

好久没写树形DP手生疏了。

题意：
每个点权值为$hp[x]+hp[v]$，其中$v$是$x$的儿子。你可以删掉$m$个点，求对于$0\le m\le n$的每个$m$能得到的最小权值和。

思路：
定义$dp[i][j][0/1]$代表点$i$为根子树，删掉了$j$个点，$i$是否被删能得到的最小权值和。
转移就是按照基本的背包转移，不再赘述。

但是注意一点，转移过程中其实隐含了$dp[i][j][0/1]$是前$x$个子树得到的结果，所以这里其实有滚动的过程，要开个临时数组。以前写这种类型题的时候由于是求最大权值和，所以可以直接转移过去，不需要滚动或者开临时数组。但是这里是取最小值，很必要，结果赛中写的时候输出的结果一直是INF ┭┮﹏┭┮。

ps:还有这个转移居然是$n^2$的，我还想着按照子树大小排个序看看能否水一水或者dfs序优化（想写，但是不知道怎么初始化状态），结果这居然是正解XD。不过冷静分析一下还是可以发现，转移实际就是枚举任意两点LCA，所以复杂度$n^2$。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;
const int maxn = 2e3 + 7;
typedef long long ll;
const ll INF = 1e18;
vector<int>G[maxn];
ll dp[maxn][maxn][2],tmp[maxn][2];
ll hp[maxn];
int siz[maxn];void dfs(int x) {siz[x] = 1;for(int t = 0;t < G[x].size();t++) {int v = G[x][t];dfs(v);for(int i = 0;i <= siz[x] + siz[v];i++) {tmp[i][0] = tmp[i][1] = INF;}for(int i = 0;i <= siz[x];i++) {for(int j = 0;j <= siz[v];j++) {tmp[i + j][0] = min(tmp[i + j][0],dp[x][i][0] + dp[v][j][0] + hp[v]);if(j > 0) {tmp[i + j][0] = min(tmp[i + j][0],dp[x][i][0] + dp[v][j][1]);}if(i > 0) {tmp[i + j][1] = min(tmp[i + j][1],dp[x][i][1] + dp[v][j][0]);}if(i > 0 && j > 0) {tmp[i + j][1] = min(tmp[i + j][1],dp[x][i][1] + dp[v][j][1]);}}}for(int j = 0;j <= siz[x] + siz[v];j++) {dp[x][j][0] = tmp[j][0];dp[x][j][1] = tmp[j][1];}siz[x] += siz[v];}for(int i = 0;i <= siz[x];i++) {dp[x][i][0] += hp[x];}
}int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) {for(int j = 0;j <= n;j++) {dp[i][j][0] = dp[i][j][1] = 0;}}for(int i = 1;i <= n;i++) G[i].clear();for(int i = 2;i <= n;i++) {int f;scanf("%d",&f);G[f].push_back(i);}for(int i = 1;i <= n;i++) {scanf("%lld",&hp[i]);}dfs(1);for(int i = 0;i <= n;i++) {printf("%lld ",min(dp[1][i][0],dp[1][i][1]));}printf("\n");}return 0;
}

这篇关于2020ICPC 南京 Monster Hunter（树形依赖背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---