h862. 超級老鼠測試 - 高中生程式解題系統

內容

貓咪是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的吉娃娃、兩歲時發明了「倒墨水」的遊戲，而現在要講的，是貓咪在國小二年級的故事。

貓咪體育課要玩「抓老鼠」的遊戲，總共要抓 $n$ 趟老鼠，在第 $i$ 趟時有老師準備好的 $a_{i}$ 隻老鼠，因為老師規定貓咪在第一趟之後的每一趟都要比前一趟抓的老鼠數目多，所以貓咪得想辦法讓 $a_{i}$ 減少或增加，貓咪可以用 $1$ 單位的力氣去抓新老鼠，讓 $a_{i}$ 增加 $1$ ，或是用 $1$ 單位的力氣將老鼠送給拉不拉多與吉娃娃，讓 $a_{i}$ 減少 $1$ 。貓咪在每一趟抓新老鼠或送老鼠的次數不限，但老鼠的數量 $a_{i}$ 不能小於 $0$ 。請問貓咪最少要花多少單位的力氣才能完成「抓老鼠」的任務呢？

輸入說明

第一行有一個正整數 $n$ ，代表要抓 $n$ 趟老鼠。

第二行有 $n$ 個非負整數 $a_{1} \sim a_{n}$ ， $a_{i}$ 代表老師在第 $i$ 天準備給貓咪的老鼠數量。

$1 \leq n \leq 2 \times 10^{5}$
$0 \leq a_{i} \leq 10^{9}$

輸出說明

輸出一個整數 $X$ ，代表貓咪如果在第一趟之後的每一趟都要比前一趟抓的老鼠數目多，最少需要花 $X$ 單位的力氣。

範例輸入 #1

5
0 2 1 1 5

範例輸出 #1

範例輸入 #2

5
157965481 134394366 394057443 615081232 457094533

範例輸出 #2

181557816

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (10%): 2.0s , <1M
不公開測資點#1 (10%): 2.0s , <1M
不公開測資點#2 (40%): 2.0s , <10M
不公開測資點#3 (40%): 2.0s , <10M

提示：

由於生測資的時候出現意外，每一行數字最後面都沒有空格。

在範例一，可以將 $a_{2}$ 減少 $1$ ，將 $a_{3}$ 增加 $1$ ，將 $a_{4}$ 增加 $2$ ，這樣新的序列會變成 $0, 1, 2, 3, 5$ ，貓咪最少可以花 $4$ 單位的力氣。

---------------------------------------------------------------------------------------------------------

$20 % ： n \leq 4000$

$80 % ：無特別限制$

標籤:

DP slope trick

出處:

[管理者：

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
36460	fire5386 (becaidorz)	h862		278	2023-07-18 17:58