回『AP325題庫』
e021: 支點切割
Tags : Basic Recursion
Accepted rate : 5人/9人 ( 56% ) [非即時]
評分方式：
Tolerant

最近更新 : 2023-12-28 19:16

Content

輸入一個大小為 N 的一維整數陣列 p[], 要找其中一個所謂的最佳切點將陣列切成左右兩塊, 然後針對左右兩個子陣列繼續切割, 切割的終止條件有兩個: 子陣列範圍小於 3 或切到給定的層級 K 就不再切割。而所謂最佳切點的要求是讓左右各點數字與到切點距離的乘積總和差異盡可能的小, 但不可以是兩端點, 也就是說, 若區段的範圍是[s,t], 則要找出切點 m∈[s+1,t-1], 使得 | SUM(p[i] × (i − m)), t times, i=s | 越小越好, 如果有兩個最佳切點, 則選擇編號較小的。所謂切割層級的限制, 第一次切以第一層計算。

Input

第一行有兩個正整數 N 與 K。第二行有 N 個正整數,代表陣列內容 p[1] ~ p[N],數字間以空白隔開,總和不超過 10^9。N ≤ 50000,切割層級限制 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 ：
Tags:
Basic Recursion
出處:
AP325 [管理者：
Eason0165 (EasonLearner)
]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」