「妁艷起床啦~~~~!」
妁艷勉強睜開眼睛,映入眼簾的是楓音那張充滿稚氣的臉。兩人的臉近到妁艷可以感覺到她呼出的氣息,妁艷連忙把她推開。
剛剛好像不小心昏過去了呢,不過話說回來,這裡是哪裡啊?妁艷心想。
「YA~妁艷醒來了~~~,」楓音坐在妁艷的腿上說道:「剛剛你在草地上昏過去了,所以我就把你搬到保健室來了。這裡的床很舒服吧~♥」
果然昏過去了,一定是今天晚上魔力什麼的消耗太多了。妁艷心想。
妁艷指著角色資料旁邊的魔力值看著楓音,「我需要補魔力了......。」
「好阿~,」楓音燦笑道:「可是為了補償我剛剛一個人很無聊,你要先陪我玩一個遊戲。」說話的同時,她拿出了一個長條型的棋盤以及M顆螢光綠的珠子。
為了盡快補完魔力找到妹妹,妁艷勉強的答應了。
遊戲規則如下:
(1) 棋盤是由N個排成一直線的格子組成的。格子由左到右邊號1~N,且每一格都有自己的高度。
(2) 在第1格有一個棋子,妁艷只能將棋子往編號大的格子移,目標是將棋子移到第N格。
(3) 用x[i]表示棋盤第i格的高度,則妁艷將棋子從第i格移到第j格(i < j)需要花max(0 , (j - i) + (x[j] - x[i]))單位的力氣。
(4) 妁艷每移動一次棋子,如果楓音手上還有珠子,她就會給他一顆。
「如果在你把棋子移到第N格的時候我手上沒有珠子了,就幫你補魔力吧~。」楓音提出條件。
因為妁艷不想花太多力氣在這個遊戲上,所以請告訴他,在花最少力氣的前提下最多可以得到幾顆珠子吧。
第一行有兩個正整數N、M,代表棋盤的格數以及楓音一開始有的珠子數。
第二行有N個整數,第i個數代表棋盤第i格的高度。
2 ≤ N ≤ 300,000
M ≤ 109
|棋盤任一格子的高度| ≤ 109
輸出一個正整數,代表妁艷在花最少力氣的前提下可以得到的珠子個數的最大值。
棋子的移動路徑:1 -> 2 -> 3 -> 4
總共移動3次,花了6單位的力氣。
原TIOJ1764 / problem setter : esrever
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 11 |
2 | 1 | 11 |
3 | 2 | 11 |
4 | 3 | 11 |
5 | 4 | 11 |
6 | 5 | 11 |
7 | 6 | 11 |
8 | 7 | 11 |
9 | 8 | 12 |