自动搬运

查看原文

来自洛谷，原作者为

	Dog_Two **

搬运于2025-08-24 21:23:10，当前版本为作者最后更新于2018-10-11 22:21:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

DP普及-，读入 IOI+

设f[i,j]表示在结点i，拿了j幅画需要的最少时间；

边界：f[u,i]=i*5(0<=i<=c[u],u是叶子结点)；

目标: max{i}(f[root][i]<tim)；

决策：f[u][i+j]=min{f[lson][i]+f[rson][j]+2*(cost[lson]+cost[rson])}；

	  即在左儿子处偷i件，在右儿子处偷j件的最小消费

读入比较麻烦，我们可以按照给定的dfs序进行递归处理（见代码）。

#include<bits/stdc++.h>
#define v first
#define w second
using namespace std;
const int maxn=600+10;
int n=1,tim;
int f[maxn][maxn];//在结点i偷到j幅画的最少时间 
int c[maxn];
vector<pair<int,int> >G[maxn];

void read(int u){
	int w,val;
	scanf("%d%d",&w,&val);
	if(val){//处理递归终点 
		G[u].push_back(make_pair(++n,w));
		c[n]=val;
		return;
	}
	G[u].push_back(make_pair(++n,w));
	int v=n;
	read(v); read(v);
	//读入v的两个儿子 
}

void input(){
	cin>>tim;
	read(1);
}

void dp(int u){
	if(G[u].empty()){
		for(int i=0;i<=c[u];++i) f[u][i]=i*5;
		return;
	}
	if(u==1){
		dp(G[u][0].v);
		f[u][0]=0;
		for(int i=1;i<=600;++i) f[u][i]=f[G[u][0].v][i]+G[u][0].w*2;
		return;
	}
	dp(G[u][0].v);
	dp(G[u][1].v);
	for(int i=0;i<=600;++i)
		for(int j=0;i+j<=600;++j){
			//经分析可知，每一层偷到的画不足120幅，这里用不影响效率的充分大数来代替 
			int lw=i?G[u][0].w:0,rw=j?G[u][1].w:0;
			f[u][i+j]=min(f[u][i+j],f[G[u][0].v][i]+f[G[u][1].v][j]+lw*2+rw*2);
		}
}

void solve(){
	memset(f,0x3f,sizeof(f));
	dp(1);
	int ans=0;
	for(int i=1;i<=600;++i) if(f[1][i]<tim) ans=i;
	cout<<ans;
}

int main(){
	input();
	solve();
	return 0;
}