Luogu P1270 “访问”美术馆 题解
Describe
题目链接
经过数月的精心准备，Peer Brelstet，一个出了名的盗画者，准备开始他的下一个行动。艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。由于经验老到，他拿下一幅画需要5秒的时间。你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。
Solution
考虑DP。
设f[i][j]表示前i个还有j秒时间。
那么易得：
由于路是要走两次的（去一次回来一次）所以t数组要乘2。
注意小偷一定要在警察来之前跑走，所以s要减一。
Code
代码语言：javascript复制#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("%dn",dfs(1,s));
}
