采访美术馆

题目

经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画。

输入输出格式

输入格式:

第1行是警察赶到的时间,以s为单位。第2行描述了艺术馆的结构,是一串非负整数,成对地出现:每一对的第一个数是走过一条走廊的时间,第2个数是它末端的藏画数量;如果第2个数是0,那么说明这条走廊分叉为两条另外的走廊。数据按照深度优先的次序给出,请看样例。

一个展室最多有20幅画。通过每个走廊的时间不超过20s。艺术馆最多有100个展室。警察赶到的时间在10min以内。

输出格式:

输出偷到的画的数量

输入输出样例

输入样例

60

7 0 8 0 3 1 14 2 10 0 12 4 6 2

输出样例

2

思路

用f[i][j] 表示从i这个节点开始话费j的时间可以摘到的最大画的数量

f[i][Time] = Max(f[lc][lcTime]+f[rc][Time-lcTime-length])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cmath>
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for (flag = false, ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) flag |= ch == '-';
for (x = 0; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
x = flag ? -x : x;
}
int T;int f[100][1000], tot;
void solve()
{
int cnt = ++ tot, length, num;
in(length); in(num);
length <<= 1;
if (num)
{
F(Time, length, T)
{
f[cnt][Time] = Min((Time - length)/5, num);
}
}
else
{
int left = tot + 1, right; solve();
right = tot + 1; solve();
F(totTime, length, T)
F(lcTime, 0, totTime-length)
f[cnt][totTime] = Max(f[cnt][totTime], f[left][lcTime] + f[right][totTime-lcTime-length]);
}
}
inline int work()
{
in(T);T --;
solve();
printf("%d\n", f[1][T]);
return 0;
}
int TAT = work();
int main() {;}