Describe
题目链接
经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画。
Solution
考虑$DP$。
设$f[i][j]$表示前$i$个还有$j$秒时间。
那么易得:
$$f[i][j]=max(f[ilson][k]+f[irson][time-t[x]-k])(0\leq k \leq time-t[x])$$
由于路是要走两次的(去一次回来一次)所以$t$数组要乘$2$。
注意小偷一定要在警察来之前跑走,所以$s$要减一。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #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)); }
|