彩彩喜歡劈瓦,所以每天都有一定數量的瓦要劈
不過劈多劈少要看狀況而定,所以有個值叫手感值 $P$ (我喜歡叫修瓦值就是了)
每天有 $a$ 份瓦,要是 $P > 0$ 就可以去劈瓦
$P \ge a$ 就能把當天的瓦都劈掉,$P$ 會減去 $a$
$P < a$ 照樣能劈,但就會直接把手感值 $P$ 用光
(也就是當天瓦可能劈不完,視 $P$ 的大小而定)
例如目前 $P = 8$
今天有 $5$ 個瓦,那決定劈的話 $P$ 就剩 $3$,共劈 $5$ 個瓦
今天有 $9$ 個瓦,那決定劈的話 $P$ 就剩 $0$,共劈 $8$ 個瓦
而當天彩彩也可以休息不去劈瓦,這天結束手感值 $P$ 會加上 $a$
但彩彩再怎麼強也是人,所以 $P$ 有個上限 $L$,且第一天開始前 $P$ 為 $0$
給定 $n$ 天的劈瓦行程表,求最大的劈瓦數
第一行給定 $n, L \space (1 \le n, L \le 3000)$ 表示共幾天要劈瓦以及手感值的上限。
第二行有 $n$ 個正整數 $ a_1, a_2, a_3, \cdots , a_i, \cdots , a_n $,$a_i$ 代表第 $ i $ 天有幾份瓦能劈 $ (0 \le a_i \le 10^ 5 ) $。
輸出彩彩最多能夠劈多少瓦
範測 2 說明
以下 sum 代表第一天到目前總共劈了多少瓦
第 1 天一定得去休息,所以該天結束後 $P = 3$
第 2 天有 $P > 0$ 了,可以開始考慮劈瓦 (彩黑) 了
若該天去劈瓦,那麼 $P = 0$,$\text{sum} = 3$
如果不去劈瓦,那麼 $P = 7$,$\text{sum} = 0$
第 3 天要劈瓦的話那要 $P > 0$,
所以從前一天來看,不去劈瓦的話才有可能
若昨天不劈今天劈,$P = 3$,$\text{sum} = 4$
所以劈瓦行程表應該要訂:不劈,不劈,劈,最多能劈 $4$ 片。
彩彩好可愛
PIXIV:79504151
No. | Testdata Range | Score |
---|---|---|
1 | 0~33 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 262144 | 65536 | |
1 | 1000 | 262144 | 65536 | |
2 | 1000 | 262144 | 65536 | |
3 | 1000 | 262144 | 65536 | |
4 | 1000 | 262144 | 65536 | |
5 | 1000 | 262144 | 65536 | |
6 | 1000 | 262144 | 65536 | |
7 | 1000 | 262144 | 65536 | |
8 | 1000 | 262144 | 65536 | |
9 | 1000 | 262144 | 65536 | |
10 | 1000 | 262144 | 65536 | |
11 | 1000 | 262144 | 65536 | |
12 | 1000 | 262144 | 65536 | |
13 | 1000 | 262144 | 65536 | |
14 | 1000 | 262144 | 65536 | |
15 | 1000 | 262144 | 65536 | |
16 | 1000 | 262144 | 65536 | |
17 | 1000 | 262144 | 65536 | |
18 | 1000 | 262144 | 65536 | |
19 | 1000 | 262144 | 65536 | |
20 | 1000 | 262144 | 65536 | |
21 | 1000 | 262144 | 65536 | |
22 | 1000 | 262144 | 65536 | |
23 | 1000 | 262144 | 65536 | |
24 | 1000 | 262144 | 65536 | |
25 | 1000 | 262144 | 65536 | |
26 | 1000 | 262144 | 65536 | |
27 | 1000 | 262144 | 65536 | |
28 | 1000 | 262144 | 65536 | |
29 | 1000 | 262144 | 65536 | |
30 | 1000 | 262144 | 65536 | |
31 | 1000 | 262144 | 65536 | |
32 | 1000 | 262144 | 65536 | |
33 | 1000 | 262144 | 65536 |