题解：P12734 理解

每个时间最多只有一个前置事件，那么事件之间的关系可以看做一个森林。题目所求的方案就是这个森林的一个子图，按照回想每个子树的根节点，再沿着树边联想的方式遍历每个关键点。代价就是选中的子图中包含的每个子树的根节点的点权和加上边权和。

还需考虑题中关于脑容量的额外限制。记脑容量为

K

的限制为限制

K

。对于一个子树，若满足限制

K

，临界情况下，以它的根节点的子节点为根节点的子树中有一个满足限制

K

，其它都满足限制

K-1

。这样我们可以先遍历满足限制

K-1

的子树，把根节点保留在脑海中以从一个子树过渡到另一个，最后遍历满足限制

K

的子树，联想得到第一个节点后就删掉根节点。

考虑 DP。设

dp_{i,j}

表示以

i

为根的子树满足限制

j

时的最小代价，不包含回想或联想事件

i

的花费。特别地，

dp_{i,0}

表示

i

不包含在所选子树中时的最小花费。如果事件

i

是关键点那就不能不选了，所以此时

dp_{i,0}=\infty

。

若不选节点

i

就无法联想它的子节点。那么有：

dp_{i,0}=\sum_{\text{j是i的子节点}}\min(dp_{j,0},dp_{j,k}+r_j)

。

同理联想其它事件时当前事件肯定还在占用脑容量，所以脑容量为

1

等于是没有，所以

dp_{i,1}=\sum_{\text{j是i的子节点}}\min(dp_{j,0},dp_{j,k}+r_j)

。

i\ge 2

时可以使用联想，有

dp_{i,u}=\sum_{\text{j是i的子节点}}\min(dp_{j,0},dp_{j,k}+r_j,dp_{j,u-1}+t_j)

。但这样的话还没有考虑其中一个子树可以满足限制

K

的情况。实现上可以先让所有子树都满足限制

K-1

，再记录考虑特殊情况后的差值，最后再更新。最后用

dp_{i,j}=min(dp_{i,j},dp_{i,j-1})

刷一遍。

答案即为所有子树的代价和：

ans=\sum_{\text{i是子树树根}} \min(dp_{i,0},dp_{i,k}+r_i)

CPP

const ll N=1e5+10,K=20,MAX=1e17;
ll n,m,k;
vector<ll> g[N];
ll r[N],t[N];
bool tg[N];
ll dp[N][K],l[N][K];

ll min3(ll a,ll b,ll c){
	return min(min(a,b),c);
}

void ini(){
	init(tg,0);
	init(dp,0);
	init(l,0);
	
	rep(i,0,N-1) g[i].clear();
}

void solve(){
	cin>>n>>m>>k;
	
	rep(i,1,n){
		ll p;
		cin>>p;
		g[p].pb(i);
	}
	
//	rep(i,0,n){
//		cout<<i<<':';
//		
//		for(ll j:g[i]) cout<<j<<' ';
//		
//		endl;
//	}
//	
//	pause;
	
	rep(i,1,n) cin>>r[i];
	
	rep(i,1,n) cin>>t[i];
	
	rep(i,1,m){
		ll p;
		cin>>p;
		tg[p]=1;
		dp[p][0]=MAX;
	}
	
	rep_(i,n,1){
		if(g[i].empty()) ctn;
		
		for(ll j:g[i]){
			ll f1,f2;
			
			rep(u,2,k){
				f1=min3(dp[j][0],dp[j][k]+r[j],dp[j][u-1]+t[j]);
				dp[i][u]+=f1;
				f2=dp[j][u]+t[j];
				update(l[i][u],f1-f2,max);
			}
			
			dp[i][1]+=min(dp[j][0],dp[j][k]+r[j]);
//			cout<<"signal 1\ndp[i][1]="<<dp[i][1]<<'\n';
//			cout<<dp[j][0]<<' '<<dp[j][k]+r[j]<<'\n';
//			pause;
		}
		
		rep(j,2,k){
			dp[i][j]-=l[i][j];
			update(dp[i][j],dp[i][j-1],min);
		}
		
		if(tg[i]==0) dp[i][0]=dp[i][1];
		
//		rep(j,0,k){
//			cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<'\n';
//			pause;
//		}
	}
	
	ll ans=0;
	
	for(ll i:g[0]) ans+=min(dp[i][0],dp[i][k]+r[i]);
	
	cout<<ans<<'\n';
}

int main(){
	ll Q;
	cin>>Q;
	
	count(Q){
		ini();
		solve();
	}
}

文章操作

相关推荐

评论

题解：P12734 理解