a039. 能量分段計畫

題目描述

有 N 個連續的能量站，第 i 個能量站的能量值為 ai。

你必須把這 N 個能量站切成剛好 K 個非空的連續區段。

對於一個區段 [l, r]，它的分數定義為： (區段總和) × (區段總和)

請找出一種切法，使得所有 K 個區段的分數總和最小。

輸入格式

第一行輸入兩個整數 N、K。 第二行輸入 N 個整數 a1、a2、...、aN。

輸出格式

輸出一個整數，代表切成剛好 K 個非空連續區段後，可以得到的最小總分。

限制

1 <= K <= N <= 500, 0 <= ai <= 10000

範例輸入 5 2 1 2 3 4 5

範例輸出 117

範例說明 最佳切法之一為：

1 2 3 | 4 5

第一段總和為 6。 第二段總和為 9。

總分為： 6 × 6 + 9 × 9 = 117