b103. Sequence - Zero1 Online Judge System

Content

給定一個長度為 $N$ 的序列 $A$，要求你把它分成恰好 $M$ 個子段。記第 $i$ 個子段左端點為 $L[i]$，右端點為 $R[i]$，則需要滿足 $L[1] = 1, L[M] = N, R[i] + 1 = L[i + 1]$ （對於所有滿足 $1 \le i \le M$ 的 $i$）。記第 $i$ 個子段的代價 $C[i] = (\sum^{R[i]}_{j=L[i]} A[j])^2$，你需要最小化並輸出所有子段的代價和 $S = \sum^M_{i=1} C[i]$。

Input

第一行兩個正整數 $N,M$
第二行 $N$ 個正整數表示序列 $A$

Output

輸出一行一個正整數表示最小的 $S$

Sample Input #1

10 3
1 1 4 5 1 4 1 9 1 9

Sample Output #1

測資資訊：

記憶體限制： 256 MB
不公開測資點#0 (3%): 1.0s , <1K
不公開測資點#1 (3%): 1.0s , <1K
不公開測資點#2 (3%): 1.0s , <1K
不公開測資點#3 (3%): 1.0s , <1K
不公開測資點#4 (3%): 1.0s , <1K
不公開測資點#5 (3%): 1.0s , <1K
不公開測資點#6 (3%): 1.0s , <1K
不公開測資點#7 (3%): 1.0s , <1K
不公開測資點#8 (3%): 1.0s , <1K
不公開測資點#9 (3%): 1.0s , <1K
不公開測資點#10 (3%): 1.0s , <1M
不公開測資點#11 (3%): 1.0s , <1M
不公開測資點#12 (3%): 1.0s , <1M
不公開測資點#13 (3%): 1.0s , <1M
不公開測資點#14 (3%): 1.0s , <1M
不公開測資點#15 (3%): 1.0s , <1M
不公開測資點#16 (3%): 1.0s , <1M
不公開測資點#17 (3%): 1.0s , <1M
不公開測資點#18 (3%): 1.0s , <1M
不公開測資點#19 (3%): 1.0s , <1M
不公開測資點#20 (4%): 2.0s , <1M
不公開測資點#21 (4%): 2.0s , <1M
不公開測資點#22 (4%): 2.0s , <1M
不公開測資點#23 (4%): 2.0s , <1M
不公開測資點#24 (4%): 2.0s , <1M
不公開測資點#25 (4%): 2.0s , <1M
不公開測資點#26 (4%): 2.0s , <1M
不公開測資點#27 (4%): 2.0s , <1M
不公開測資點#28 (4%): 2.0s , <1M
不公開測資點#29 (4%): 2.0s , <1M

Hint ：

1 ≤ M ≤ N ≤ 2 × 10⁵

1 ≤ A[i] ≤ 10⁴

子任務

1. （30分）N ≤ 100

2. （30分）M ≤ 50

3. （40分）没有額外的約束條件。

Tags:

動態規劃

出處:

PCOI 2023 第一季 [管理者：

1164120-7@g.... (hcng)

]

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