|
【样例输入】
|
【样例输出】
|
|
70 3
71 100
69 1
1 2
|
3
|
|
16 5
5 4
8 9
7 5
3 4
6 9
|
18
|
二维数组，填表格方法。
以第二组数据为例。假设我们要的答案就是f[5,16],就是眼前有5颗宝石且你有16秒的时间，你能取得的最大的价值量。
假如第5颗宝石你不想取，那么f[5,16]=f[4,16]
假如第5颗宝石你想拿，那么 f[5,16]=f[4,10]+9
所以 f[5,16]=max( f[4,16] ,
f[4,10]+9)
16 5
5 4
8 9
7 5
3 4
6 9
具体实现如下表格：
|
f[i,j]
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
1
|
0
|
0
|
0
|
0
|
0
|
4
|
4
|
4
|
4
|
4
|
4
|
4
|
4
|
4
|
4
|
4
|
4
|
|
2
|
0
|
0
|
0
|
0
|
0
|
4
|
4
|
4
|
9
|
9
|
9
|
9
|
9
|
13
|
13
|
13
|
13
|
|
3
|
0
|
0
|
0
|
0
|
0
|
4
|
4
|
5
|
9
|
9
|
9
|
9
|
9
|
13
|
13
|
14
|
14
|
|
4
|
0
|
0
|
0
|
4
|
4
|
4
|
4
|
5
|
9
|
9
|
9
|
13
|
13
|
13
|
13
|
14
|
17
|
|
5
|
0
|
0
|
0
|
4
|
4
|
4
|
9
|
9
|
9
|
13
|
13
|
13
|
13
|
14
|
18
|
18
|
18
|