a413. APCS 2018/02：支點切割 (ZeroJudge f638)

題目描述

對陣列區段 [s,t] 選一個非端點 m 作切點，使 |Σ p[i]×(i−m)| 最小，求和範圍為 s 到 t。若有並列最佳值，取索引較小者。切點本身取出，剩下的 [s,m−1] 與 [m+1,t] 分別繼續切割。區段不足 3 個元素時不切割；最多切到第 K 層，第一次切割為第 1 層。計算所有被選切點的元素值總和。

輸入格式

第一行為正整數 N、K，N ≤ 50000，K < 30。第二行為 N 個正整數 p[1] 到 p[N]，其總和不超過 10^9。

輸出格式

輸出所有切點上的 p 值之和。

來源：https://zerojudge.tw/ShowProblem?problemid=f638