你好！我是你的OI教练。我们已经顺利完成了“标准划分”、“数量约束”和“长度限制”的专项训练。现在，我们进入这个专题的最后一关：状态转移算子的灵活替换。

在NOI竞赛中，DP的模板是死的，但题目要求的“代价（Cost）”是活的。讲义在第24页和30页特别提醒：当你改变题目目标（如求最小值、求最大值的最小值等）时，最需要改动的是状态转移方程中的算子。

本题将带你练习最经典的“最小化最大值（Minimax）”模型，并要求你通过本专题学到的空间压缩技巧来实现它。

题目四：分割数组的最大值最小化 (Split Array Largest Sum)

【题目描述】

给定一个包含 $N$ 个正整数的数组 $A$，以及一个正整数 $K$。 你需要将数组 $A$ 恰好划分为 $K$ 个非空且连续的子数组。 我们定义一个划分方案的“代价”为：这 $K$ 个子数组各自的元素之和中的最大值。 请你设计一个算法，求出所有合法划分方案中，能够获得的最小代价。

【输入格式】

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

【输出格式】

输出到标准输出。 输出一个整数，表示所有方案中“各子数组和的最大值”的最小值。

【样例输入 1】

5 2
7 2 5 10 8

【样例输出 1】

18

【样例 1 说明】

将数组划分为 2 段，可能的方案有：

• [7] 和 [2, 5, 10, 8]：和分别为 7, 25。最大值为 25。
• [7, 2] 和 [5, 10, 8]：和分别为 9, 23。最大值为 23。
• [7, 2, 5] 和 [10, 8]：和分别为 14, 18。最大值为 18。
• [7, 2, 5, 10] 和 [8]：和分别为 24, 8。最大值为 24。 其中最大值的最小值是 18。

【样例输入 2】

5 3
1 2 3 4 5

【样例输出 2】

6

【数据范围与提示】

• $1 \le N \le 200$
• $1 \le K \le \min(N, 50)$
• $1 \le A_i \le 10^6$
• 结果保证在 32 位整数范围内。

💡 教练的赛场指引 (涵盖讲义所有进阶优化知识点)

这道题考察的是你对 DP 转移方程中“算子”的理解。请根据讲义内容在草稿纸上完成以下推理：

1. 转移算子的替换 (Changing the Operator)

• 基础模型回顾：在第一题中，我们求的是“和的最大值”，转移方程是 $dp[i][j] = \max(dp[x][j-1] + \text{cost})$。
• 本题逻辑推导：
  • 我们要让各段和的“最大值”尽量小。
  • 假设前 $x$ 个元素分成 $j-1$ 段的最大和是 $dp[x][j-1]$。
  • 最后一段（第 $j$ 段）的和是 $\text{sum}(x+1, i)$。
  • 那么前 $i$ 个元素分成 $j$ 段后，总体的最大和就是 $\max(dp[x][j-1], \text{sum}(x+1, i))$。
  • 我们要从所有可能的分割点 $x$ 中选一个，使得这个总体最大和最小。
• 👉 新方程：$dp[i][j] = \min_{j-1 \le x < i} \{ \max(dp[x][j-1], \text{sum}(x+1, i)) \}$

2. 初始化与无效状态 (Starting Point & Infinity)

• 起点的中性值：讲义第5页提到，求最小值问题时，无效状态必须标记为正无穷（INT_MAX）。
• Logical Origin：$dp[0][0] = 0$。表示 0 个元素分 0 段的最大和是 0。
• Base Case (j=1)：第一列 $dp[i][1]$ 应该是前 $i$ 个元素的累加和（因为一段的最大和就是它自己）。

3. 空间优化的极限挑战 (Rolling Array)

• 讲义第15、16页强调：为了节省空间，可以使用一维数组。
• 倒序遍历的重要性：在本题中，计算 $dp[i]$ 需要用到上一轮 $j-1$ 的旧值 $dp[x]$。由于 $x < i$，如果正序更新，$dp[x]$ 就会被本轮新值覆盖。因此，内层 $i$ 循环必须从 $N$ 递减到 $j$。

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

为了避免 Mermaid 渲染错误，流程图中的逻辑判断均使用安全文字描述。

graph TD
    A(开始算法) --> B(计算数组前缀和 prefix)
    B --> C(定义一维 DP 数组大小为 N 加 1)
    
    C --> D(初始化: dp 0 位置设为 0, 其余位置设为正无穷)
    
    D --> E(处理基准情况 j 等于 1: 遍历 i 从 1 到 N)
    E --> F(dp 的第 i 项赋值为 prefix 的第 i 项)
    
    F --> G(外层循环 j: 划分段数从 2 到 K)
    G --> H{j 小于等于 K 吗}
    H -- 否: 循环结束 --> Z(返回最终答案 dp 的 N 项)
    
    H -- 是 --> I(内层循环 i: 逆序遍历 从 N 递减到 j)
    I --> J{i 大于等于 j 吗}
    
    J -- 否: i 循环结束 --> G1(j 增加 1)
    G1 --> H
    
    J -- 是 --> K(临时变量 cur_min 设为正无穷)
    K --> L(分割点 x 循环: 从 j 减 1 遍历到 i 减 1)
    L --> M{x 小于 i 吗}
    
    M -- 否: x 循环结束 --> N(更新 dp 的第 i 项为 cur_min)
    N --> I1(i 减小 1)
    I1 --> J
    
    M -- 是 --> O(计算最后一段的和 last_sum: 等于 prefix_i 减去 prefix_x)
    O --> P(计算当前方案最大值 tmp_max: 等于 dp_x 与 last_sum 的较大者)
    P --> Q(更新 cur_min: 取 cur_min 与 tmp_max 的较小者)
    Q --> L1(x 增加 1)
    L1 --> M

🧠 读题理解意图的关键词 (Key Terms)

在NOI读题时，看到以下组合请立刻联想到此模型：

1. “划分” + “连续子数组”：确定 DP 结构。
2. “最大值最小化”：确定状态转移中的 min(max(...)) 算子。
3. “恰好 K 个”：确定最终目标状态为 $dp[N][K]$ 或一维压缩后的 $dp[N]$。
4. “正整数”：这是一个重要的隐藏信息，意味着前缀和是单调递增的，这保证了我们的分割点 $x$ 范围推导是安全的。

🏆 复杂度分析思考过程

1. 时间复杂度：

   • 状态数 $O(N \times K)$。
   • 每个状态转移遍历分割点 $O(N)$。
   • 前缀和预处理使得区间求和为 $O(1)$。
   • 总复杂度 $O(N^2 K)$。在 $N=200, K=50$ 规模下，计算次数约为 $200 \times 200 \times 50 = 2 \times 10^6$，在 NOIP 1秒时限内绰绰有余。

2. 空间复杂度：

   • 使用一维滚动数组，空间复杂度 $O(N)$。对于 $N=200$ 而言，内存占用几乎可以忽略不计。

当你准备好实现这份代码时，请随时呼唤我，我将为你展示如何用最简洁的代码处理这种“双重最优化算子”的嵌套！