思路概述

若最后一段以位置 $i$ 结尾、上一段结尾在 $t-1$ 处（即最后一段是 $[t,i]$ ），则该段贡献为 $\min\limits_{x\in[t,i]} a_x$ 。设 $dp[j][i]$ 表示将前 $i$ 个数分成 $j$ 段的最大和，则有

题目内容

小 A 正在分析一份由 $n$ 条记录组成的日志文件，每条记录都有一个重要度评分。为了便于归档，他需要将日志文件分割成 $k$ 个连续且非空的片段。

每个片段的价值定义为该片段中最低的重要度评分。小 A 希望所有片段的价值总和尽可能大。

请你帮助小 A 计算可以获得的最大总价值。

日志记录的数量 $n$ 不超过 $10^4$ ，片段数量 $k$ 满足 $1 \le k \le \min(n, 100)$ ，每条记录的重要度评分均为 $1$ 到 $100$ 之间的整数。