Luogu P1270 “访问”美术馆 题解

#include<bits/stdc++.h>
using namespace std;
int s,t[1010],a[1010],f[1010][1010];
inline void init(int x){
scanf("%d%d",&t[x],&a[x]);
t[x]*=2;
if(!a[x]) init(x<<1),init(x<<11);
}
inline int dfs(int x,int tim){
if(!tim) return 0;
if(f[x][tim]) return f[x][tim]; 
if(a[x]) return f[x][tim]=min(a[x],(tim-t[x])/5);
for(int i=0;i<=tim-t[x];i++)
f[x][tim]=max(f[x][tim],dfs(x<<1,i)+dfs(x<<11,tim-t[x]-i));
return f[x][tim];
}
int main(){
scanf("%d",&s);--s;
init(1);
printf("%d\n",dfs(1,s));
}