一、问题分析与数学建模

1.1 问题本质

这是一道动态规划 + 单调队列优化的经典问题，核心在于理解子任务的得分机制并设计高效的状态转移。

问题形式化

给定：

• $N$ 个选手，$T$ 组测试数据
• 分数数组 $\texttt{Points}[1..T]$，其中 $\texttt{Points}[i]$ 表示第 $i$ 组测试数据的分数
• 结果矩阵 $\texttt{Results}[1..N][1..T]$，其中 $\texttt{Results}[i][j] = 1$ 表示第 $i$ 个选手通过了第 $j$ 组测试数据

子任务定义：

• 将 $T$ 组测试数据划分成 $K$ 个连续的子任务（$1 \le K \le S$）
• 每个子任务包含连续的测试数据区间

得分规则： 对于选手 $i$ 和子任务 $[l, r]$：

$$\text{Score}_i([l,r]) = \begin{cases} \sum_{j=l}^{r} \texttt{Points}[j] & \text{如果选手 } i \text{ 通过了 } [l,r] \text{ 中所有测试数据} \\ 0 & \text{否则} \end{cases} $$

目标：对于每个 $1 \le K \le S$，求将测试数据分成恰好 $K$ 个子任务时，所有选手得分之和的最小值。

---

1.2 核心数学观察

观察 1：选手通过子任务的充要条件

命题 1：选手 $i$ 通过子任务 $[l, r]$ 当且仅当对于所有 $l \le j \le r$，都有 $\texttt{Results}[i][j] = 1$。

推论：如果选手 $i$ 在区间 $[l, r]$ 中有任意一个测试数据未通过，则该选手在这个子任务中得 0 分。

---

观察 2：预处理最后出错位置

为了快速判断选手是否通过某个子任务，我们定义：

定义：$\texttt{pre}[i][j]$ 表示选手 $i$ 在位置 $j$ 或之前最后一次出错的位置。

形式化定义：

$$\texttt{pre}[i][j] = \begin{cases} j & \text{如果 } \texttt{Results}[i][j] = 0 \\ \texttt{pre}[i][j-1] & \text{如果 } \texttt{Results}[i][j] = 1 \end{cases} $$

关键性质：选手 $i$ 通过子任务 $[k+1, j]$ 当且仅当 $\texttt{pre}[i][j] \le k$。

证明：

• 若 $\texttt{pre}[i][j] \le k$，则选手 $i$ 在 $[k+1, j]$ 区间内没有出错，因此通过该子任务 ✓
• 若 $\texttt{pre}[i][j] > k$，则选手 $i$ 在 $[k+1, j]$ 区间内至少有一次出错，因此得 0 分 ✓

---

观察 3：动态规划状态设计

状态定义：

$$\texttt{dp}[i][j] = \text{前 } i \text{ 组测试数据分成 } j \text{ 个子任务时的最小总分} $$

初始状态：

$$\texttt{dp}[0][0] = 0, \quad \texttt{dp}[i][j] = +\infty \text{ (其他)} $$

目标答案：

$$\texttt{dp}[T][K] \quad (K = 1, 2, \ldots, S)$$

---

观察 4：状态转移方程

考虑最后一个子任务 $[k+1, j]$（$0 \le k < j$），则：

$$\texttt{dp}[j][x+1] = \min_{k=x-1}^{j-1} \left\{ \texttt{dp}[k][x] + \text{cost}(k+1, j) \right\} $$

其中 $\text{cost}(k+1, j)$ 表示子任务 $[k+1, j]$ 的总得分：

$$\text{cost}(k+1, j) = \text{cnt}(k, j) \times \sum_{i=k+1}^{j} \texttt{Points}[i] $$

这里 $\text{cnt}(k, j)$ 表示能够通过子任务 $[k+1, j]$ 的选手数量：

$$\text{cnt}(k, j) = \left| \{ i : \texttt{pre}[i][j] \le k \} \right| $$

直观理解：

• 如果有 $\text{cnt}$ 个选手通过了子任务 $[k+1, j]$
• 每个选手获得的分数是 $\sum_{i=k+1}^{j} \texttt{Points}[i]$
• 因此这个子任务的总得分是两者的乘积

---

1.3 朴素算法的复杂度瓶颈

朴素动态规划的时间复杂度为 $O(T^2 \cdot S)$，对于 $T \le 2 \times 10^4$ 的数据规模，会超时。

瓶颈分析：

• 外层循环：$S$ 个子任务
• 中层循环：$T$ 个结束位置 $j$
• 内层循环：$T$ 个起始位置 $k$

需要优化内层循环。

---

二、算法优化：单调队列优化 DP

2.1 转移方程的变形

将状态转移方程改写：

$$\texttt{dp}[j][x+1] = \min_{k} \left\{ \texttt{dp}[k][x] + \text{cnt}(k, j) \times \left( \texttt{sum}[j] - \texttt{sum}[k] \right) \right\} $$

其中 $\texttt{sum}[i] = \sum_{t=1}^{i} \texttt{Points}[t]$ 是分数的前缀和。

展开：

$$\texttt{dp}[j][x+1] = \min_{k} \left\{ \texttt{dp}[k][x] + \text{cnt}(k, j) \times \texttt{sum}[j] - \text{cnt}(k, j) \times \texttt{sum}[k] \right\} $$

由于 $\text{cnt}(k, j) \times \texttt{sum}[j]$ 对于固定的 $j$ 和不同的 $k$ 可能不同（因为 $\text{cnt}$ 依赖于 $k$），我们需要重新组织。

---

2.2 按 $\texttt{cnt}$ 值分组

关键观察：对于固定的 $j$，随着 $k$ 从小到大变化，$\text{cnt}(k, j)$ 是单调非递减的。

证明：

• $\text{cnt}(k, j) = \left| \{ i : \texttt{pre}[i][j] \le k \} \right|$
• 当 $k$ 增大时，满足条件的选手数量只会增加或保持不变 ✓

进一步观察：$\text{cnt}(k, j)$ 的取值只会在某些特殊的 $k$ 值处发生变化，这些特殊值恰好是 $\texttt{pre}[i][j]$（对于所有选手 $i$）。

分组策略： 将所有 $\texttt{pre}[1][j], \texttt{pre}[2][j], \ldots, \texttt{pre}[N][j]$ 收集起来并排序，记为 $p_1 < p_2 < \ldots < p_m$。

对于 $k \in [p_t, p_{t+1})$，$\text{cnt}(k, j)$ 的值是固定的，等于 $t$（有 $t$ 个选手的 $\texttt{pre}$ 值 $\le k$）。

---

2.3 单调队列维护最小值

对于每个 $\text{cnt}$ 值（记为 $c$），我们需要维护：

$$\min_{k \in [p_t, p_{t+1})} \left\{ \texttt{dp}[k][x] - c \times \texttt{sum}[k] \right\} $$

然后加上 $c \times \texttt{sum}[j]$ 得到最终的转移值。

单调队列优化：

• 对于每个 $c$ 值，维护一个单调队列
• 队列中存储 $(\text{位置} k, \texttt{dp}[k][x] - c \times \texttt{sum}[k])$
• 队列保持单调递增，队首是最小值
• 当 $k$ 的范围变化时，动态更新队列

---

2.4 算法流程总结

对于第 $x+1$ 个子任务（基于前 $x$ 个子任务的结果）：

1. 初始化：为每个可能的 $\text{cnt}$ 值创建一个单调队列
2. 枚举结束位置 $j = x+1, x+2, \ldots, T$：
   • 收集所有 $\texttt{pre}[i][j]$ 的值，加入 $0$ 和 $j$，排序得到分界点
   • 对于每个区间 $[p_t, p_{t+1})$，$\text{cnt}$ 值为 $t$：
     • 更新第 $t$ 个单调队列，将区间 $[p_t, p_{t+1})$ 内的转移点加入
     • 从队首取出最小值，加上 $t \times \texttt{sum}[j]$，更新 $\texttt{dp}[j][x+1]$

---

三、代码模块详解

模块 1：头文件与全局变量

#include <bits/stdc++.h>
#define re register
#define int long long
#define chmin(a,b) (a = min(a,b))

using namespace std;

typedef pair<int, int> pii;
const int N = 2e4 + 10, M = 60;
const int inf = (int)(1e18) + 10;

int n, m, S;
char s[M][N];
int arr[N], sum[N];
int pre[M][N], dp[N][M];

数据结构说明：

• n：选手数量 $N$
• m：测试数据数量 $T$
• S：最大子任务数
• s[i][j]：第 $i$ 个选手在第 $j$ 组测试数据的结果（'0' 或 '1'）
• arr[i]：第 $i$ 组测试数据的分数
• sum[i]：分数的前缀和，$\texttt{sum}[i] = \sum_{j=1}^{i} \texttt{arr}[j]$
• pre[i][j]：选手 $i$ 在位置 $j$ 或之前最后一次出错的位置
• dp[i][j]：前 $i$ 组测试数据分成 $j$ 个子任务的最小总分

---

模块 2：单调队列结构

struct {
    int L, R;
    deque<pii> q;

    inline void clear() {
        L = 0, R = -1;
        while (!q.empty())
            q.pop_back();
    }

    inline void update(int l, int r, int x, int cnt) {
        // 扩展右边界，加入新的转移点
        while (R < r) {
            R++;
            int val = dp[R][x] - cnt * sum[R];
            
            // 维护单调性：弹出所有 >= val 的元素
            while (!q.empty() && q.back().snd >= val)
                q.pop_back();
            
            q.push_back({R, val});
        }

        // 收缩左边界，移除不在范围内的元素
        while (L < l) {
            while (!q.empty() && q.front().fst <= L)
                q.pop_front();
            
            L++;
        }
    }
} mq[M];

单调队列的关键操作：

1. clear()：清空队列，重置边界

   • L 和 R 记录当前维护的区间 $[L, R]$

2. update(l, r, x, cnt)：更新队列以维护区间 $[l, r]$

   • 扩展右边界：将 $[R+1, r]$ 内的点加入队列

     • 计算转移值：$\texttt{val} = \texttt{dp}[R][x] - \texttt{cnt} \times \texttt{sum}[R]$
     • 维护单调性：弹出队尾所有 $\ge \texttt{val}$ 的元素
     • 将新元素加入队尾

   • 收缩左边界：移除 $[L, l)$ 内的点

     • 如果队首元素的位置 $\le L$，则弹出
     • 更新 $L$

单调性质：队列中的元素按照转移值单调递增，队首是最小值。

数学推导： 对于固定的 $\text{cnt}$ 值，转移方程变为：

$$\texttt{dp}[j][x+1] = \min_{k \in [l, r]} \left\{ \texttt{dp}[k][x] - \text{cnt} \times \texttt{sum}[k] \right\} + \text{cnt} \times \texttt{sum}[j] $$

单调队列维护的是 $\texttt{dp}[k][x] - \text{cnt} \times \texttt{sum}[k]$ 的最小值。

---

模块 3：输入与预处理

signed main() {
    n = read(), m = read(), S = read();

    // 读入分数并计算前缀和
    for (re int i = 1; i <= m; i++)
        sum[i] = sum[i - 1] + (arr[i] = read());

    // 读入结果矩阵并预处理 pre 数组
    for (re int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);

        for (re int j = 1; j <= m; j++) {
            if (s[i][j] == '0')
                pre[i][j] = j;  // 当前位置出错
            else
                pre[i][j] = pre[i][j - 1];  // 继承上一个出错位置
        }
    }

预处理逻辑：

1. 前缀和计算：

   $$\texttt{sum}[i] = \sum_{j=1}^{i} \texttt{arr}[j]$$

   用于快速计算子任务 $[k+1, j]$ 的分数和：$\texttt{sum}[j] - \texttt{sum}[k]$

2. pre 数组的递推：

   • 如果 $s[i][j] = 0$（出错），则 $\texttt{pre}[i][j] = j$
   • 如果 $s[i][j] = 1$（通过），则 $\texttt{pre}[i][j] = \texttt{pre}[i][j-1]$

   正确性：这样递推后，$\texttt{pre}[i][j]$ 始终保存了选手 $i$ 在 $[1, j]$ 区间内最后一次出错的位置（如果从未出错，则为 0）。

---

模块 4：动态规划主循环

    // 初始化 DP 数组
    for (re int i = 0; i <= m; i++) {
        for (re int j = 0; j <= S; j++)
            dp[i][j] = inf;
    }
    dp[0][0] = 0;

    // 枚举子任务数
    for (re int i = 0; i < S; i++) {
        // 清空所有单调队列
        for (re int j = 0; j <= n; j++)
            mq[j].clear();

        // 枚举当前子任务的结束位置
        for (re int j = i + 1; j <= m; j++) {
            vector<int> pt;

            // 收集所有分界点
            for (re int k = 1; k <= n; k++) {
                pt.push_back(pre[k][j]);
            }
            pt.push_back(0);
            pt.push_back(j);
            sort(pt.begin(), pt.end());

外层循环：枚举已有的子任务数 $i$，计算 $i+1$ 个子任务的情况。

中层循环：枚举当前子任务的结束位置 $j$。

收集分界点：

• 将所有 $\texttt{pre}[k][j]$（$k = 1, 2, \ldots, n$）收集到 pt 中
• 加入 $0$（下界）和 $j$（上界）
• 排序后去重

分界点的意义：

• 在区间 $[\texttt{pt}[p], \texttt{pt}[p+1])$ 内，能通过子任务 $[k+1, j]$ 的选手数量是固定的，等于 $p$
• 因此可以按照选手数量分组处理

---

模块 5：分组转移与单调队列优化

            for (re int p = 0; p < pt.size() - 1; p++) {
                if (pt[p] == pt[p + 1])
                    continue;

                // 更新第 p 个单调队列，维护区间 [pt[p], pt[p+1]-1]
                mq[p].update(pt[p], pt[p + 1] - 1, i, p);
                
                // 从队首取出最小值，更新 dp[j][i+1]
                chmin(dp[j][i + 1], mq[p].q.front().snd + p * sum[j]);
            }
        }
    }

分组转移的核心逻辑：

对于每个分界点区间 $[\texttt{pt}[p], \texttt{pt}[p+1])$：

1. 跳过空区间：如果 $\texttt{pt}[p] = \texttt{pt}[p+1]$，说明没有新的转移点

2. 更新单调队列：

   • 调用 mq[p].update(pt[p], pt[p+1]-1, i, p)
   • 将区间 $[\texttt{pt}[p], \texttt{pt}[p+1]-1]$ 内的转移点加入第 $p$ 个队列
   • 队列中维护的是 $\texttt{dp}[k][i] - p \times \texttt{sum}[k]$ 的最小值

3. 计算转移值：

   • 从队首取出最小值：$\texttt{minval} = \texttt{dp}[k][i] - p \times \texttt{sum}[k]$
   • 加上当前项：$\texttt{minval} + p \times \texttt{sum}[j]$
   • 更新 $\texttt{dp}[j][i+1]$

数学推导：

$$\begin{aligned} \texttt{dp}[j][i+1] &= \min \left\{ \texttt{dp}[k][i] + p \times (\texttt{sum}[j] - \texttt{sum}[k]) \right\} \\ &= \min \left\{ \texttt{dp}[k][i] - p \times \texttt{sum}[k] \right\} + p \times \texttt{sum}[j] \\ &= \texttt{mq}[p].q.\text{front}().\text{snd} + p \times \texttt{sum}[j] \end{aligned} $$

为什么要分组？

• 因为不同的 $k$ 值对应不同的 $\text{cnt}$ 值
• 只有 $\text{cnt}$ 值相同时，才能用统一的公式计算
• 分组后，每组内的转移系数（$\text{cnt} \times \texttt{sum}[j]$）是相同的

---

模块 6：输出答案

    for (re int i = 1; i <= S; i++)
        printf("%lld\n", dp[m][i]);

    return 0;
}

输出：对于每个 $i = 1, 2, \ldots, S$，输出 $\texttt{dp}[m][i]$，即将所有 $m$ 组测试数据分成 $i$ 个子任务时的最小总分。

---

四、正确性证明

4.1 状态转移的正确性

定理 1：状态转移方程正确刻画了问题的递推关系。

证明：

• 考虑前 $j$ 组测试数据分成 $i+1$ 个子任务
• 最后一个子任务为 $[k+1, j]$（$0 \le k < j$）
• 前 $k$ 组数据分成 $i$ 个子任务，最优值为 $\texttt{dp}[k][i]$
• 子任务 $[k+1, j]$ 的得分为 $\text{cnt}(k, j) \times (\texttt{sum}[j] - \texttt{sum}[k])$
• 总分为两者之和，取最小值即得 $\texttt{dp}[j][i+1]$ ✓

---

4.2 单调队列优化的正确性

定理 2：单调队列正确维护了区间最小值。

证明：

• 队列中的元素按照转移值单调递增
• 队首元素是最小值
• 当新元素加入时，弹出所有 $\ge$ 新值的元素，保持单调性
• 当区间收缩时，弹出不在范围内的元素
• 因此队首始终是当前区间的最小值 ✓

---

4.3 分组策略的正确性

定理 3：按照 $\texttt{pre}$ 值分组后，每组内的 $\text{cnt}$ 值是固定的。

证明：

• 对于固定的 $j$，$\text{cnt}(k, j) = \left| \{ i : \texttt{pre}[i][j] \le k \} \right|$
• 当 $k \in [\texttt{pt}[p], \texttt{pt}[p+1])$ 时，满足 $\texttt{pre}[i][j] \le k$ 的选手数量恰好为 $p$
• 因此 $\text{cnt}(k, j) = p$ 在该区间内是常数 ✓

---

五、复杂度分析

5.1 时间复杂度

预处理：

• 读入并计算前缀和：$O(T)$
• 预处理 pre 数组：$O(N \times T)$

动态规划：

• 外层循环：$O(S)$
• 中层循环：$O(T)$
• 收集分界点并排序：$O(N \log N)$
• 分组转移：对于每个 $j$，每个转移点 $k$ 至多被加入队列一次，至多被弹出一次，因此均摊 $O(T)$

总时间复杂度：

$$O(N \times T + S \times T \times (N \log N + T))$$

简化为：

$$O(S \times T \times N \log N)$$

对于 $N \le 50, T \le 2 \times 10^4, S \le 50$，约为 $5 \times 10^7$ 次操作，可以通过。

---

5.2 空间复杂度

• dp 数组：$O(T \times S)$
• pre 数组：$O(N \times T)$
• 单调队列：$O(N \times T)$（最坏情况）

总空间复杂度：$O(N \times T + T \times S)$

---

六、算法总结与启发

6.1 核心思想

本题采用的动态规划 + 单调队列优化算法的核心思想：

1. DP 建模：将问题抽象为划分问题，设计 DP 状态和转移方程
2. 预处理优化：预处理 pre 数组，快速判断选手是否通过子任务
3. 分组转移：按照选手数量分组，将不同 $\text{cnt}$ 值的转移分开处理
4. 单调队列优化：对于每个 $\text{cnt}$ 值，使用单调队列维护区间最小值，降低时间复杂度

---

6.2 关键技巧

1. 预处理最后出错位置：

   • 通过递推快速计算 pre 数组
   • 利用 pre 数组快速判断选手是否通过子任务

2. 分组转移：

   • 观察到 $\text{cnt}(k, j)$ 只在特殊位置变化
   • 按照 $\text{cnt}$ 值分组，避免重复计算

3. 单调队列优化：

   • 将区间最小值查询从 $O(T)$ 优化到均摊 $O(1)$
   • 关键是维护队列的单调性

---

6.3 适用场景

• ✅ 区间划分问题
• ✅ DP 转移需要维护区间最小值/最大值
• ✅ 转移系数分段恒定的问题
• ✅ 需要单调队列优化的 DP

---

七、易错点与注意事项

7.1 易错点 1：pre 数组的初始化

错误做法：忘记初始化 pre[i][0] = 0

正确做法：

• 如果选手从未出错，pre[i][j] 应该保持为 0
• 递推时正确继承上一个状态

---

7.2 易错点 2：分界点的处理

错误做法：忘记加入 0 和 $j$ 作为边界

正确做法：

• 必须加入 $0$（下界），表示没有选手通过的情况
• 必须加入 $j$（上界），确保所有转移点都被覆盖

---

7.3 易错点 3：单调队列的边界

错误做法：队列的左右边界 L 和 R 初始化错误

正确做法：

• 初始时 L = 0, R = -1，表示空区间
• 更新时先扩展右边界，再收缩左边界

---

7.4 易错点 4：数据类型溢出

问题：$N \times (\texttt{Points}[1] + \ldots + \texttt{Points}[T]) \le 2 \times 10^9$，需要使用 long long

解决：代码中使用 #define int long long，确保所有整数运算都是 64 位的。

---

八、知识点总结

8.1 核心算法技巧

1. ✅ 动态规划

   • 区间划分 DP
   • 状态设计与转移

2. ✅ 单调队列

   • 维护区间最小值
   • 均摊 $O(1)$ 查询

3. ✅ 预处理优化

   • 前缀和
   • 最后出错位置的递推

4. ✅ 分组优化

   • 按照转移系数分组
   • 避免重复计算

---

九、总结

本题是一道经典的动态规划优化问题，综合考察了：

• DP 状态设计与转移
• 预处理技巧
• 单调队列优化
• 分组处理技巧