CF643C Levels and Regions

Radewoosh 正在玩一款电脑游戏。游戏共有 $n$ 个关卡，编号为 $1$ 到 $n$。关卡被划分为 $k$ 个区域（分组）。每个区域包含若干个连续的关卡，且每个区域至少有一个关卡。 游戏会重复如下流程： 1. 如果所有区域都已经通关，则游戏立即结束。否则，系统会找到第一个还有未被通关的关卡的区域，记为 $X$。 2. 系统为代币准备一个空袋子。每个代币代表一个关卡，同一个关卡可以有多个代币进入袋子。 - 对于 $X$ 区域内已经通关的每个关卡 $i$，系统会向袋子中加入 $t_i$ 个代表第 $i$ 关的代币。 - 令 $j$ 为 $X$ 区域中第一个未通关的关卡，系统会向袋子中加入 $t_j$ 个代表第 $j$ 关的代币。 3. 最后，系统会从袋子里等概率随机抽取一个代币，玩家将游玩该代币所代表的关卡。玩家每玩一次关卡，无论该关卡是否已经通关，都会花费一小时，且视为通过一次该关卡。 给定 $n$、$k$ 以及 $t_1, t_2, \ldots, t_n$，请你将关卡划分到不同的区域（每个关卡属于且只属于一个区域，每个区域内包含不为空的连续关卡）。问：以最优方式划分区域后，完成游戏所需期望时间的最小值是多少？

第一行输入两个整数 $n$ 和 $k$（$1 \leq n \leq 200\,000$，$1 \leq k \leq \min(50, n)$），分别表示关卡数和区域数。 第二行输入 $n$ 个整数 $t_1, t_2, \ldots, t_n$（$1 \leq t_i \leq 100\,000$）。

输出一个实数，表示按最优方式分区后，完成游戏所需期望小时数的最小值。输出答案的绝对误差或相对误差不超过 $10^{-4}$ 即视为正确。 即，假设你的答案为 $a$，标准答案为 $b$。如果满足 $|a-b| \leq 10^{-4} \cdot \max(1, |b|)$ 则认为正确。

在第一个样例中，应将 $4$ 个关卡分为 $2$ 个区域。最优方案是让第一个区域包含且仅包含第一个关卡（必须是第一个关卡）。那么第二个区域应包含剩下的三个关卡。 在第二个样例中，最优方案是将关卡划分为两个区域，每个区域包含 $3$ 个关卡。 由 ChatGPT 5 翻译