d004: 習題 Q-1-4. 支點切割 (APCS201802) (@@)
Tags : Recursion prefix sum
Accepted rate : 18人/37人 ( 49% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-28 10:13

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
7 3
2 4 1 3 7 6 9
Sample Output
11
測資資訊:
記憶體限制: 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{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
58
s1060119@cdsh.i... (JBM_David)
d004
解題方向
48 2021-02-18 20:59
46
Superdanby (Superdanby)
d004
107 2020-12-27 01:26