题解：P9634 [ICPC 2020 Nanjing R] Monster Hunter

思路

引入了限制几次操作，容易想到是树上背包。

每个点都有两种状态：使用魔法和不使用，因此初次设计状态时引入一维来记录是否操作以便转移（这类题若写出方程后发现状态不独立再去掉这维）。

我们定义

dp_{u,i,0/1}

表示在

u

子树内使用了

i

次魔法，根节点使用/不使用魔法的最小代价（注意这里我用

0

代表使用了魔法，即根节点不贡献代价）。

若根节点使用魔法，代价是所有子树最小代价的和。树上背包我们做的实际上是子树一个个合并，我们可以把根节点本身当做一个子树参与合并。

若根节点使用魔法，肯定已经使用一次了 ~~（废话）~~，自身代价为

0

：

dp_{u,1,0}=0

若根节点不使用，自身的血量肯定要贡献代价：

dp_{u,0,1}=hp_u

对于子树

v

，若根节点使用魔法，儿子节点的血量不用贡献代价，反之则根据儿子节点是否使用了魔法决定：

dp_{u,i+j,0}=dp_{u,i,0}+\min(dp_{v,j,0},dp_{v,j,1})\\ dp_{u,i+j,1}=dp_{u,i,1}+\min(dp_{v,j,0},dp_{v,j,1}+hp_v)

细节

转移时复制一个副本以防新状态覆盖旧状态导致错误转移。

显然一个子树能用多少次魔法取决于其大小，转移时，若根节点使用魔法，

i

必须从

1

开始循环，到

size_u

结束；若不使用则从

0

开始，到

size_u-1

结束，最后把根节点的 DP 值全部输出即可。

code

#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int MAXN=2e3+10;
int t,n;
vector<int> a[MAXN];
int hp[MAXN],dp[MAXN][2][MAXN];
int tmp[2][MAXN],siz[MAXN];
int min(int x,int y){
	return x<y?x:y;
}
void dfs(int x){
	dp[x][0][1]=0;
	dp[x][1][0]=hp[x];
	siz[x]=1;
	for(int v:a[x]){
		dfs(v);
		for(int i=0;i<=siz[x];++i){
			tmp[0][i]=dp[x][0][i];
			dp[x][0][i]=0x3f3f3f3f3f3f3f3fll;
			tmp[1][i]=dp[x][1][i];
			dp[x][1][i]=0x3f3f3f3f3f3f3f3fll;
		}
		for(int i=0;i<=siz[x];++i){
			for(int j=0;j<=siz[v];++j){
				if(i>0){
					dp[x][0][i+j]=min(dp[x][0][i+j],tmp[0][i]+min(dp[v][0][j],dp[v][1][j]));
				}
				if(i<siz[x]){
					dp[x][1][i+j]=min(dp[x][1][i+j],tmp[1][i]+min(dp[v][0][j],dp[v][1][j]+hp[v]));
				}
			}
		}
		siz[x]+=siz[v];
	}
}
signed main()
{
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;++i){
			a[i].clear();
			for(int j=0;j<=n;++j){
				dp[i][0][j]=dp[i][1][j]=0x3f3f3f3f3f3f3f3fll;
			}
		}
		for(int i=2;i<=n;++i){
			int p;
			cin>>p;
			a[p].emplace_back(i);
		}
		for(int i=1;i<=n;++i){
			cin>>hp[i];
		}
		dfs(1);
		for(int i=0;i<=n;++i){
			cout<<min(dp[1][0][i],dp[1][1][i])<<' ';
		}
		cout<<endl;
	}
	return 0;
}

题解：P9634 [ICPC 2020 Nanjing R] Monster Hunter

文章操作

思路

细节

code

相关推荐

评论

题解：P9634 [ICPC 2020 Nanjing R] Monster Hunter