d004. 習題 Q-1-4. 支點切割 (APCS201802) (@@)

Content

輸入一個大小為 $N$ 的一維整數陣列 $p[]$，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個:子陣列範圍小於 $3$ 或切到給定的層級 $K$ 就不再切割。

而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，也就是說，若區段的範圍是$[s,t]$，則要找出切點 $m \in [s+1,t-1]$，使得 $|\sum_{i=s}^t{p[i] \times (i- m)}|$ 越小越好，如果有兩個最佳切點，則選擇編號較小的。

Input

第一行有兩個正整數 $N$ 與 $K$。

第二行有 $N$ 個正整數，代表陣列內容 $p[1]$ ~ $p[N]$，

數字間以空白隔開，總和不超過$10^9,N \leq50000$，切割層級限制 $K<30$。

Output

所有切點的 $p[ ]$值總和。

Sample Input #1

7 3
2 4 1 3 7 6 9

Sample Output #1

Sample Input #2

5 1
1 2 3 4 100

Sample Output #2

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

Hint ：

注意overflow

Tags:

Recursion prefix sum

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]