a149:
Q-1-4. 支點切割 (APCS201802)
內容
輸入一個大小為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 3 2 4 1 3 7 6 9
範例輸出
#1
11
範例輸入
#2
5 1 1 2 3 4 100
範例輸出
#2
4
測資資訊：
記憶體限制：
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
公開 測資點#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
提示 ：
範例一說明：第一層切在7，切成第二層的[2,4,1,3]與[6,9]。左邊[2,4,1,3]切在4與1都是最佳，選擇4來切，切成[2]與[1,3]，右邊[6,9]不到3個就不切了。第三層都不到3個，所以終止。總計切兩個位置7+4=11。
範例二說明：第一層切在4(注意切點不可在端點)，切出[1,2,3]與[100]，因為K=1，所以不再切。
標籤:
出處:
AP325
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||