我们现在正式进入 【变体一：数量约束】。

在真实的 NOI/CSP 赛场上，出题人非常喜欢在“划分次数”上做文章。本题将完全涵盖讲义中 "Exactly K vs. At Most K" (恰好 K 个 vs. 最多 K 个) 的全部核心知识点。

请准备好草稿纸，留意题目中加粗的字眼，这往往是决定生死边界的关键！

题目二：最多 K 个分区的最大平均值和 (Largest Sum of Averages - At Most K)

【题目描述】

给定一个包含 $N$ 个整数的数组 $A$（注意：元素可能为负数或零），以及一个正整数 $K$。 你需要将数组 $A$ 划分为 最多 $K$ 个 非空且连续的子数组。 我们定义一个划分方案的“收益”为：这些子数组的平均值之和。 请你设计一个算法，求出所有合法划分方案中，能够获得的最大收益。

【输入格式】

从标准输入读入数据。 第一行包含两个正整数 $N$ 和 $K$，分别表示数组的长度和允许划分的最多段数。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，相邻两个数之间用空格隔开，表示数组的元素。

【输出格式】

输出到标准输出。 输出一个实数，表示能获得的最大平均值之和。你的输出与标准答案的绝对误差或相对误差在 $10^{-5}$ 以内即被视为正确。（建议输出保留 $6$ 位小数）。

【样例输入 1】

3 3
-10 -10 -10

【样例输出 1】

-10.000000

【样例 1 说明】

最多划分 3 段。我们来看看所有可能的划分方案：

• 划分 1 段：[-10, -10, -10]，平均值为 -10.0。
• 划分 2 段：[-10] 和 [-10, -10]，平均值之和为 -10.0 + (-10.0) = -20.0。
• 划分 3 段：[-10]，[-10] 和 [-10]，平均值之和为 -10.0 - 10.0 - 10.0 = -30.0。 因为是求最大收益，所以最优解是只划分 1 段，收益为 -10.0。这证明了当允许“最多”且存在负收益时，划分更多段并不总是更好的。

【样例输入 2】

5 3
9 1 2 3 9

【样例输出 2】

20.000000

【数据范围与提示】

• $1 \le N \le 100$
• $1 \le K \le N$
• $-10^4 \le A_i \le 10^4$
• 保证所有计算过程中的数据不会超过 C++ 中 double 类型的表示范围。

💡 教练的赛场指引 (涵盖讲义核心知识点)

这道题是考察你对 DP 状态定义理解深度的试金石。请在草稿纸上对照以下几点进行推演：

1. 核心变化：恰好 K 个 vs. 最多 K 个 (Exactly K vs. At Most K)

• 状态转移的底层逻辑不变 (Transitions Remain Identical)：讲义（Page 11）明确指出，无论题目要求“恰好”还是“最多”，dp(i, j) 的计算过程和状态转移方程是完全相同的。依然是 $dp(i, j) = \max \{ dp(x-1, j-1) + \text{cost}(x, i) \}$。
• 最终答案的定义发生改变 (Only the Conclusion Changes)：
  • 如果是“恰好 K 个”，你只需要盯着目的地，答案必定在 dp(N, K) 这个单一单元格中。
  • 如果是“最多 K 个”，说明你可以在划分 1 段、2 段、... 一直到 K 段的任何时刻“停下”。讲义提供了一个绝佳的记忆技巧 (Memory trick, Page 32)：“恰好”意味着你需要精确的目的地；“最多”意味着你需要检查所有有效的最终状态并挑选出最好的一个。
  • 因此，最终答案是集合 $\{ dp(N, 1), dp(N, 2), \dots, dp(N, K) \}$ 中的最大值。

2. 初始化与边界情况 (Handling Constraints)

• 由于包含了负数，无效状态 dp(0, j) (将 0 个元素划分为 $j>0$ 段) 初始化时依然必须使用一个足够小的负无穷大（如 -1e9），防止其干扰正常转移。
• dp(i, 1)（第一列，划分 1 段）依然是后续所有计算的基石，必须优先预处理。

3. 一维空间优化的隐藏陷阱 (Space Optimization Pitfall)

• 在第一题中，我们学习了将 DP 表从 $O(N \times K)$ 压缩到 $O(N)$。
• 教练的灵魂拷问：如果你使用一维滚动数组 dp(i)，在全部循环结束后，dp(N) 里存的是什么？
  • 答案：存的仅仅是恰好划分 $K$ 段时的最优解！因为之前的 $j=1, 2, \dots, K-1$ 的结果在滚动更新中已经被覆盖掉了！
• 如何解决？：如果坚持使用一维滚动数组，你必须在每一次外层 $j$ 循环结束时，主动将当前的 dp(N) 拿出来，去更新一个全局的最大值变量 Global_Max。这一点是许多选手在赛场上翻车的重灾区。

📐 算法逻辑伪代码 (C++14 风格流程设计)

教练为你准备了结合了空间优化（一维滚动数组）和最多 K 个答案收集的流程图。请注意观察，我们在哪里收集了最终答案。

(注：为避免渲染错误，流程图中的判断和赋值均使用纯中文或安全符号描述)

graph TD
    A(开始算法) --> B(定义全局最优解 Global_Max 赋值为负无穷)
    B --> C(计算数组的前缀和 prefix)
    
    C --> D(初始化一维 dp 数组大小为 N 加 1, 全部填入负无穷)
    
    D --> E(处理基准情况 j 等于 1: 遍历 i 从 1 到 N)
    E --> F(dp 的第 i 项赋值为 prefix 的第 i 项除以 i)
    F --> G(循环结束: 提取第一段的最优解)
    
    G --> H(Global_Max 赋值为 dp 的第 N 项与 Global_Max 的较大值)
    
    H --> I(外层循环 j: 划分段数从 2 到 K)
    I --> J{j 小于等于 K 吗}
    J -- 否: 循环结束 --> Z(返回最终答案 Global_Max)
    
    J -- 是 --> K(中层循环 i: 逆序遍历 从 N 递减到 j)
    K --> L{i 大于等于 j 吗}
    
    L -- 否: i 循环结束 --> M(收集当前 j 段划分的最优解)
    M --> N(Global_Max 赋值为 dp 的第 N 项与 Global_Max 的较大值)
    N --> I1(j 增加 1)
    I1 --> J
    
    L -- 是 --> O(临时变量 max_val 赋值为负无穷)
    O --> P(内层循环 x: 分割点从 j 到 i)
    P --> Q{x 小于等于 i 吗}
    
    Q -- 否: x 循环结束 --> R(安全更新: dp 的第 i 项赋值为 max_val)
    R --> K1(i 减小 1)
    K1 --> L
    
    Q -- 是 --> S(计算最后一段从 x 到 i 的平均值 avg)
    S --> T(状态转移: max_val 取 max_val 与 dp的第x减1项加avg 的较大值)
    T --> P1(x 增加 1)
    P1 --> Q

🧠 复杂度与优化思考总结

• 时间复杂度：尽管我们在收集答案，但主体依然是三重循环嵌套，寻找最值的操作 $O(K)$ 被平摊或隐藏在循环间隙中，整体时间复杂度保持为 $O(N^2 K)$。
• 空间复杂度：我们坚持使用了 dp(N) 的一维数组，通过极其精妙的 Global_Max 变量接力，成功在空间复杂度 $O(N)$ 的极限状态下，求出了“最多 $K$ 次”的正确答案。

当你完全理解了这个流程图，并能把它在脑海中转化为 C++14 的代码后，你对这一类 DP 的掌控力就已经击败了 80% 的选手。接下来，随时告诉我，我们将向更具挑战的**【变体二：附带最小长度限制的 K 次划分】**进发！