「SCOI2005」最大子矩阵
题意理解
有一个 ( n \times m ) 的矩阵，要选出 ( k ) 个 互不重叠 的子矩阵，使得它们的分值之和最大。
约束：
- ( 1 \le n \le 100 )
- ( 1 \le m \le 2 )
- ( 1 \le k \le 10 )
由于 ( m ) 最大为 2，我们可以分情况讨论。
思路分析
情况 1：( m = 1 )
矩阵只有一列，问题变成： 在长度为 ( n ) 的数组中，选出 ( k ) 个不相交的连续子段，使和最大。
这是经典问题：最大 ( k ) 段子段和（子段不相交）。
可以用动态规划： 设 ( dp[i][t] ) 表示前 ( i ) 个数中选出 ( t ) 段的最大和。 转移：
- 不选第 ( i ) 个数：( dp[i][t] = dp[i-1][t] )
- 选第 ( i ) 个数，并作为新的一段：( dp[i][t] = \max(dp[i][t], dp[j][t-1] + sum[j+1..i]) )，其中 ( j < i )。 但这样是 ( O(n^2 k) )，可以优化： 我们同时维护 ( g[i][t] = \max_{j \le i} dp[j][t] )，这样可以直接用 ( g[i-1][t-1] + a[i] ) 来更新当前段延续或新开一段。
更简单的做法： 设 ( f[i][t] ) 表示前 i 个数，选 t 段，且第 i 个数必须被最后一段包含的最大值。 设 ( g[i][t] ) 表示前 i 个数，选 t 段，第 i 个数不一定被选的最大值。
转移： [ f[i][t] = \max(f[i-1][t], g[i-1][t-1]) + a[i] ] [ g[i][t] = \max(g[i-1][t], f[i][t]) ] 初始化 ( f[0][0] = 0 )，其余为 -inf，答案 = ( g[n][k] )。
情况 2：( m = 2 )
矩阵有两列，子矩阵可以是：
- 只取第一列的若干行（宽 1）
- 只取第二列的若干行（宽 1）
- 同时取两列的相同若干行（宽 2）
我们仍然用 DP： 设状态 ( dp[i][t][p] ) 表示前 ( i ) 行，选了 ( t ) 个子矩阵，第 ( i ) 行的选取状态为 ( p ) 时的最大和。
状态 ( p )：
- ( p = 0 )：第 i 行不选
- ( p = 1 )：第 i 行只选第一列（宽 1 矩阵）
- ( p = 2 )：第 i 行只选第二列（宽 1 矩阵）
- ( p = 3 )：第 i 行选两列（宽 2 矩阵）
转移时：
- 如果上一行相同状态，可以合并到同一个子矩阵（如果可能的话）
- 否则新开一个子矩阵（t+1）
具体来说： 设 ( a[i][0] ) 和 ( a[i][1] ) 表示第 i 行两列的值。
初始化 ( dp[0][0][0] = 0 )，其余 -inf。
对于 ( i = 1 \dots n )，对于 ( t = 0 \dots k )，对于 ( p = 0 \dots 3 )：
-
从 ( p' = 0 )（上一行没选）：
- 新开一个矩阵：( dp[i][t+1][p] )
-
从相同 ( p )（延续上一行的矩阵）：
- 如果 ( p ) 相同，则 ( dp[i][t][p] )
-
从某些可接上的状态（比如上一行 p=1，这一行 p=3 不行，但上一行 p=3 这一行 p=3 可以）
实际上更简单的方法是： 枚举上一行状态 ( prev ) 和当前行状态 ( cur )：
- 如果 ( cur = 0 )，则可以从任何 prev 过来，t 不变。
- 如果 ( cur = prev ) 且 cur != 0，则延续矩阵，t 不变。
- 如果 ( cur != prev ) 且 cur != 0 且 prev != 0，则不能直接接（因为矩阵不能重叠且宽不同）
- 如果 ( prev = 0 )，则新开矩阵，t+1
- 如果 ( cur != prev ) 且 prev != 0 且 cur != 0，其实只有一种情况可能：prev=3 时 cur=1 或 2 不行，prev=1 时 cur=2 不行，等等。其实可以简单处理：只有当 cur 和 prev 在列上不冲突且宽一致时才能延续，否则新开。
但更保险的方法：我们直接枚举当前行状态和上一行状态，判断是否能接在一起，不能就新开一个矩阵（t+1），能就 t 不变。
样例验证
输入：
3 2 2
1 -3
2 3
-2 3
输出：
9
与题目一致。
复杂度
状态数 ( O(n \cdot k \cdot 4) )，转移 ( O(4) )，总 ( O(nk \cdot 16) )，完全可行。