APCS201802第3題支點切割

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

輸入一個大小為N的一維整數陣列p[]，要找其中一個所謂的最佳切點將陣列切成左右兩塊，然後針對左右兩個子陣列繼續切割，切割的終止條件有兩個：子陣列範圍小於3或切到給定的層級K就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小，但不可以是兩端點，也就是說，若區段的範圍是[s,t]，則要找出切點 m ∈ [s+1,t-1]，使得

越小越好，如果有兩個最佳切點，則選擇編號較小的。所謂切割層級的限制，第一次切以第一層計算。

輸入說明

輸入格式：第 一行 有兩 個正整數 N 與 K 。 第二行 有 N 個正整數 代表陣列內容 p[1] ~ p [N 數字間以空白隔開， 總和不超過 10^9。 N ≤ 50000，切割層級限制K<30。

輸出說明

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

輸入範例1

7 1

2 4 1 3 7 6 9

輸出範例1

7

說明

選擇7，將第二層分成左邊[2 4 1 3]與右邊[6,9]， 

左邊為2*(-4)+4*(-3)+1*(-2)+3*(-1)=-25，右邊為9*2+6*1=24，左右兩邊加總為1。

輸入範例2

7 3

2 4 1 3 7 6 9

輸出範例2

11

第一層選擇7，將第二層分成左邊[2 4 1 3]與右邊[6,9]， 

左邊為2*(-4)+4*(-3)+1*(-2)+3*(-1)=-25，右邊為9*2+6*1=24，左右兩邊加總為1。

第二層[2 4 1 3]選擇4或1都是5，4在左邊所以選擇4，左邊[2]右邊[1 3]

左邊2*(-1)=-2，右邊3*2+1*1=7，左右兩邊加總為5。

第二層[6,9]因為個數小於3所以不用處理。

第三層以後都小於3個元素，不用處理。

7+4=11

解題策略

前綴和、後綴和與遞迴