s797. 菇菇栽培 - 高中生程式解題系統

內容

不倒翁學長經營著一座現代化的高科技菇菇栽培場。栽培場內共有 N（1≤N≤200000）個菇菇栽培床，依序編號為 1 至 N。由於不同品種的菇菇對生長環境的要求不同，第 i 個栽培床的菇菇有其對應的最低濕度需求值 H_i（1≤H_i≤10⁶）。

為了方便管理並節省資源，學長計畫將這 N 個栽培床切分成若干個連續的溫室區塊（每個栽培床必須剛好屬於一個區塊）。對於每一個劃分出來的區塊，學長必須安裝一套獨立的中央調控系統，該系統的單次固定安裝成本為 P（1≤P≤10⁹）。

為了確保該區塊內所有菇菇都能順利長大，中央調控系統必須將該區塊的濕度維持在該區塊內所有栽培床的濕度需求最大值。若一個區塊包含自栽培床 i 到 j （i≤j）的所有床位，則該系統維持濕度所需的營運成本，為該區塊維持的濕度值乘以該區塊內的床位總數。因此，設置該區塊的總花費為：
Cost(i, j) = max_{i ≤ k ≤ j} H_k × (j − i + 1) + P

下圖為一個 N=5, P=5 的範例，格子中的數字代表各個栽培床的濕度需求，如果我們將栽培床分割成 [10] [2, 2] [10] [2] 四個區塊，可以僅花費最小成本：

(10 × 1 + 5) + (2 × 2 + 5) + (10 × 1 + 5) + (2 × 1 + 5) = 46

就讓每一個栽培床滿足濕度需求。

10	2	2	10	2

請你寫一個程式，協助不倒翁學長，計算出在滿足所有栽培床濕度需求的條件下，所需的最小總花費成本為多少。

輸入說明

第一行包含兩個正整數 N 與 P，分別代表菇菇栽培床的總數，以及每套調控系統的固定安裝成本。

第二行包含 N 個正整數 H₁, H₂, …, H_n，依序代表各個栽培床的濕度需求值。

輸出說明

請輸出一個整數，代表將所有栽培床分區後的最小總花費成本。

範例輸入 #1

5 5
10 2 2 10 2

範例輸出 #1

範例輸入 #2

6 20
50 60 70 80 90 100

範例輸出 #2

測資資訊：

記憶體限制： 256 MB
不公開測資點#0 (5%): 1.0s , <10M
不公開測資點#1 (5%): 1.0s , <10M
不公開測資點#2 (5%): 1.0s , <10M
不公開測資點#3 (5%): 1.0s , <10M
不公開測資點#4 (5%): 1.0s , <1M
不公開測資點#5 (5%): 1.0s , <1M
不公開測資點#6 (5%): 1.0s , <10M
不公開測資點#7 (5%): 1.0s , <10M
不公開測資點#8 (5%): 1.0s , <1M
不公開測資點#9 (5%): 1.0s , <10M
不公開測資點#10 (5%): 1.0s , <10M
不公開測資點#11 (5%): 1.0s , <10M
不公開測資點#12 (5%): 1.0s , <10M
不公開測資點#13 (5%): 1.0s , <10M
不公開測資點#14 (5%): 1.0s , <1M
不公開測資點#15 (5%): 1.0s , <1M
不公開測資點#16 (5%): 1.0s , <1M
不公開測資點#17 (5%): 1.0s , <1M
不公開測資點#18 (5%): 1.0s , <1K
不公開測資點#19 (5%): 1.0s , <1K

提示：

標籤:

AM系列題目

出處:

[管理者：

lsstmoonis@g ... (CERE) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」