Subarray Squares

题目描述

给定一个包含 $n$ 个元素的数组，你的任务是将其划分为 $k$ 个子数组。每个子数组的代价是该子数组内元素和的平方。若你采取最优策略，最小的总代价是多少？

输入格式

第一行包含两个整数 $n$ 和 $k$：数组的长度以及子数组的数量。数组元素按 $1,2,\dots,n$ 编号。 第二行包含 $n$ 个整数 $x_1,x_2,\dots,x_n$：数组的内容。

输出格式

输出一个整数：最小的总代价。

8 3
2 3 1 2 2 3 4 1

110

提示

$1 \le k \le n \le 3000$ $1 \le x_i \le 10^5$ 样例解释：一个最优解为 [2,3,1], [2,2,3], [4,1]，其代价为 $(2+3+1)^2+(2+2+3)^2+(4+1)^2=110。

标签: CSES2086|先进技术

来源

CSES2086|先进技术