輸入一個大小為 $N$ 的一維整數陣列 $p$，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於 3 或切到給定的層級 $K$ 就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，但不可以是兩端點，也就是說，若區段的 範圍是$[s,t]$，則要找出切點 $m \in [s+1,t-1]$，使得$\begin{vmatrix}\sum\limits_{i=s}^{t} p[i] \times (i-m)\end{vmatrix}$ 越小越好，如果有兩個最佳切點，則選擇編號較小的。所謂切割層級的限制，第一次切以第一層計算。
第一行有兩個正整數 $N$ 與 $K$ 。第二行有 $N$ 個正整數，代表陣列內容 $p[1]$ ~ $p[N]$，數字間以空白隔開，每個數字不超過 105，總和不超過 109。N ≤ 50000，切割層級限制 $K<30$ 。
所有切點的 p值總和。
7 3 2 4 1 3 7 6 9
11
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||