P1270 “访问”美术馆 题解

Link

P1270 “访问”美术馆

solve

这道题给出的结构都是树形的，所以很容易就看出是树形DP，我们定义(F[i][j])表示走到第i条边，还有j秒时间能拿的最大画数，对于尽头是展室的能拿则拿，尽头是走廊的我们枚举分到不同走廊的时间，用记忆化DFS来实现就好了。

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int Tim,cost[maxn*10],val[maxn*10],F[maxn][maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void init(int x){
	cost[x]=read()*2,val[x]=read();
	if(!val[x]){init(x<<1);init(x<<1|1);}
}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int DFS(int x,int tim){
	if(F[x][tim]>0||tim==0)return F[x][tim];
	if(val[x])return F[x][tim]=min(val[x],(tim-cost[x])/5);
	for(int i=0;i<=tim-cost[x];i++){
		F[x][tim]=max(F[x][tim],DFS(x<<1,i)+DFS(x<<1|1,tim-cost[x]-i));
	}
	return F[x][tim];
}
int main(){
	freopen("P1270.in","r",stdin);
	freopen("P1270.out","w",stdout);
	Tim=read()-1;
	init(1);
	printf("%d
",DFS(1,Tim));
	return 0;
}