版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P2258] [NOIP2014 普及组] 子矩阵" categories:
给出如下定义:
子矩阵: 从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵 (保持行与列的相对顺序) 被称为原矩阵的一个子矩阵
例如, 下面左图中选取第 $2$, $4$ 行和第 $2$, $4$, $5$ 列交叉位置的元素得到一个 $2 \times 3$ 的子矩阵如右图所示
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1
的其中一个 $2 \times 3$ 的子矩阵是
4 7 4
8 6 9
相邻的元素: 矩阵中的某个元素与其上下左右四个元素 (如果存在的话) 是相邻的
矩阵的分值: 矩阵中每一对相邻元素之差的绝对值之和
本题任务: 给定一个 $n$ 行 $m$ 列的正整数矩阵, 请你从这个矩阵中选出一个 $r$ 行 $c$ 列的子矩阵, 使得这个子矩阵的分值最小, 并输出这个分值
(本题目为 2014NOIP 普及 T4)
第一行包含用空格隔开的四个整数 $n,m,r,c$, 意义如问题描述中所述, 每两个整数之间用一个空格隔开
接下来的 $n$ 行, 每行包含 $m$ 个用空格隔开的整数, 用来表示问题描述中那个 $n$ 行 $m$ 列的矩阵
一个整数, 表示满足题目描述的子矩阵的最小分值
5 5 2 3
9 3 3 3 9
9 4 8 7 4
1 7 4 6 6
6 8 5 6 9
7 4 5 6 1
6
7 7 3 3
7 7 7 6 2 10 5
5 8 8 2 1 6 2
2 9 5 5 6 1 7
7 9 3 6 1 7 8
1 9 1 4 7 8 8
10 5 9 1 1 8 10
1 3 1 5 4 8 6
16
【输入输出样例 1 说明】
该矩阵中分值最小的 $2$ 行 $3$ 列的子矩阵由原矩阵的第 $4$ 行, 第 $5$ 行与第 $1$ 列, 第 $3$ 列, 第 $4$ 列交叉位置的元素组成, 为
6 5 6
7 5 6
其分值为: |6-5| + |5-6| + |7-5| + |5-6| + |6-7| + |5-5| + |6-6| =6
【输入输出样例 2 说明】
该矩阵中分值最小的 3 行 3 列的子矩阵由原矩阵的第 $4$ 行, 第 $5$ 行, 第 $6$ 行与第 $2$ 列, 第 $6$ 列, 第 $7$ 列交叉位置的元素组成, 选取的分值最小的子矩阵为
9 7 8
9 8 8
5 8 10
【数据说明】
对于 $50\%$ 的数据, $1 \leq n \leq 12,1 \leq m \leq 12$, 矩阵中的每个元素 $1 \leq a_{ij} \leq 20$
对于 $100\%$ 的数据, $1 \leq n \leq 16,1 \leq m \leq 16$, 矩阵中的每个元素 $1 \leq a_{ij} \leq 1,000,1 \leq r \leq n,1 \leq c \leq m$
显然 DP, 如果是一维的情况, 显然就是个区间 DP
令 $f(i,j)$ 表示选第 $i$ 个且已选 $j$ 个时候的最优值, 则
$$ f(i,j)=\min{f(i',j-1)+|a_{i'}-a_i|} $$
二维的做法相同, 这时候我们要开四维数组
令
则
$$ f(i,j,k,l)=\min\left{f(i',j-1,k',l-1)+\sum{u\in K}|a{i',u}-a{i,u}|+\sum{v\in I}|a{v,k'}-a{v,k}|+S(I,K)\right} $$
可以使用状态压缩来将 DP 数组变为三维, 方法是对某一方向上的方案进行状态压缩, 如行的选择方案
注意要剪枝, 如当前选择行的个数不为 $r$ 则跳过
$O\left({n\choose \frac{n}{2}}m^3\right)$ 或 $O\left({m\choose \frac{m}{2}}n^3\right)$