Yet Another Partiton Problem

题意翻译

给定数组 $a_1,a_2\cdots a_n$，你需要将它划分成 $k$ 段（每个元素在且仅在一段中），某段 $a_l,a_{l+1}\cdots a_r$ 的权值为 $(r-l+1)\times \max_{l\leq i\leq r}\{a_i\}$，整个划分的权值是每段权值之和。求最小划分权值。 $n \leq 2 \times 10^4$，$k \leq 100$。

题目描述

You are given array $ a_1, a_2, \dots, a_n $ . You need to split it into $ k $ subsegments (so every element is included in exactly one subsegment). The weight of a subsegment $ a_l, a_{l+1}, \dots, a_r $ is equal to $ (r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i) $ . The weight of a partition is a total weight of all its segments. Find the partition of minimal weight.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^4 $ , $ 1 \le k \le \min(100, n) $ ) — the length of the array $ a $ and the number of subsegments in the partition. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 2 \cdot 10^4 $ ) — the array $ a $ .

输出格式

Print single integer — the minimal weight among all possible partitions.

输入输出样例

输入样例 #1

4 2
6 1 7 4

输出样例 #1

25

输入样例 #2

4 3
6 1 7 4

输出样例 #2

21

输入样例 #3

5 4
5 1 5 1 5

输出样例 #3

21

说明

The optimal partition in the first example is next: $ 6 $ $ 1 $ $ 7 $ $ \bigg| $ $ 4 $ . The optimal partition in the second example is next: $ 6 $ $ \bigg| $ $ 1 $ $ \bigg| $ $ 7 $ $ 4 $ . One of the optimal partitions in the third example is next: $ 5 $ $ \bigg| $ $ 1 $ $ 5 $ $ \bigg| $ $ 1 $ $ \bigg| $ $ 5 $ .