「SCOI2005」最大子矩阵 题解

            题意简述

给定一个 $n \times m$ 的矩阵，要求选出恰好 $k$ 个互不重叠的子矩阵，使得这些子矩阵包含的元素分值之和达到最大。子矩阵之间不能有任何重叠部分，每个元素的分值可以是正数或负数。

算法思路

              问题分析

本题的关键约束在于矩阵的列数 $m$ 最多为 $2$，这一特殊条件使得我们可以采用分类讨论的策略，将原本复杂的二维问题转化为相对简单的一维或准一维动态规划问题。

单列情况（$m = 1$） 当矩阵只有一列时，问题简化为在长度为 $n$ 的序列中选取 $k$ 个不相交的子段，使得子段和最大。

采用动态规划解决，定义状态表示考虑前 $i$ 个元素、已经选取了 $j$ 个子矩阵时的情况，并通过两个状态分别记录当前元素是否被选中。状态转移时考虑延续已有子矩阵或新建子矩阵的决策。

双列情况（$m = 2$） 当矩阵有两列时，情况较为复杂。我们采用五种状态来精确描述每一行的选择情况：

两列均不选：当前行不参与任何子矩阵

仅选第一列：当前行第一列单独构成或延续一个子矩阵

仅选第二列：当前行第二列单独构成或延续一个子矩阵

两列同属一个子矩阵：当前行两列作为一个整体参与同一个子矩阵

两列分属不同子矩阵：当前行两列分别参与两个不同的子矩阵

状态转移时需要细致考虑各种可能的延续和新建情况，特别是当选择两列作为不同子矩阵时，需要消耗两个子矩阵名额。

算法特点 这种解法充分利用了数据范围的特殊性，通过精细的状态设计完整覆盖了所有可能的选择情况。对于单列情况采用经典的最大$k$子段和模型，对于双列情况则通过扩展状态空间来准确描述行列选择的各种组合，最终通过动态规划高效求解。