目录题目题解题目给出如下定义子矩阵从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵保持行与列的相对顺序被称为原矩阵的一个子矩阵。例如下面左图中选取第 2 、 4 行和第 2 、 4 、 5 列交叉位置的元素得到一个 2×3 的子矩阵如右图所示。相邻的元素矩阵中的某个元素与其上下左右四个元素如果存在的话是相邻的。矩阵的分值矩阵中每一对相邻元素之差的绝对值之和。本题任务给定一个 n 行 m 列的正整数矩阵请你从这个矩阵中选出一个 rr 行 cc 列的子矩阵使得这个子矩阵的分值最小并输出这个分值。输入格式输入第一行包含用空格隔开的四个整数 n,m,r,c 意义如问题描述中所述每两个整数之间用一个空格隔开。接下来的 nn 行每行包含 m 个用空格隔开的整数用来表示问题描述中那个 n 行 m 列的矩阵。输出格式一个整数表示满足题目描述的子矩阵的最小分值。数据范围对于 50% 的数据 1≤n≤12 , 1≤m≤12 矩阵中的每个元素 1 \le a_{ij} \le 201≤aij​≤20 对于 100\%100% 的数据 1 \le n \le 161≤n≤16 , 1 \le m \le 161≤m≤16 矩阵中的每个元素 1 \le a_{ij} \le 1,0001≤aij​≤1,000 , 1 \le r \le n,1 \le c \le m1≤r≤n,1≤c≤m 。样例说明样例1该矩阵中分值最小的 22 行 33 列的子矩阵由原矩阵的第 44 行、第 55 行与第 11 列、第 33 列、第 44 列交叉位置的元素组成为6 5 6 7 5 6其分值为: |6-5| |5-6| |7-5| |5-6| |6-7| |5-5| |6-6| 6∣6−5∣∣5−6∣∣7−5∣∣5−6∣∣6−7∣∣5−5∣∣6−6∣6。样例2该矩阵中分值最小的3行3列的子矩阵由原矩阵的第 44 行、第 55 行、第 66 行与第 22 列、第 66 列、第 77 列交叉位置的元素组成选取的分值最小的子矩阵为9 7 8 9 8 8 5 8 10输出时每行末尾的多余空格不影响答案正确性要求使用「文件输入输出」的方式解题输入文件为matrix.in输出文件为matrix.out样例输入15 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样例输出16样例输入27 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样例输出216题解知识点动态规划二进制枚举子集分析首先这道题目我们可以很容易想到暴力 如果剪枝得当是可以 AC 的。这道题目比较好的方法是 DP。当选定的行固定时问题变成给定一个长度为 m 的序列从中选出一个长度为 c 的子序列。序列中的每个元素均有一个分值且任意相邻两个被选出的元素也会产生一个分值。问如何选择子序列可使分值之和最小。这是一个经典的序列DP模型状态表示f[i][j]表示所有以第i个数结尾且长度为j的子序列的分值之和的最小值。状态计算以倒数第二个数是哪个数为依据将f[i][j]所代表的集合分成若干类则倒数第二个数是第k个数的所有子序列的最小分值是f[k][j - 1] cost()其中cost是在序列末尾加上第i个数所产生的分值。f[i][j]取所有类别的最小分值即可。其中1、cw[i]表示第i列所贡献的上下之间的分值。2、rw[i][j]表示第i列与第j列所贡献的左右之间的分值。注意题意里说的是先取一个子矩阵然后是这个子矩阵里相邻的两数的分值。3、f[i][j]表示当前选到第i列一共选了j列的最小分值。所以把 i 这一列加入的时候需要加上第 i 列上下之间的分值以及 第 i 列和上一列 第 k 列 的左右之间的分值。读者可以自己模拟一遍或者用C输出一下数据。代码#includecstring #includeiostream #includealgorithm #includecmath #includecstdio using namespace std; const int N 20, INF 1e9; int n, m, r, c; int matrix[N][N]; int f[N][N]; int cw[N], rw[N][N]; int q[N]; int count(int x){ int s 0; for (int i 0; i n; i ) s x i 1; return s; } int main(){ freopen(matrix.in,r,stdin); freopen(matrix.out,w,stdout); cin n m r c; for (int i 0; i n; i ) for (int j 0; j m; j ) cin matrix[i][j]; int res INF; for (int state 0; state 1 n; state ) if (count(state) r){ for (int i 0, j 0; i n; i ) if (state i 1) q[j ] i; for (int i 0; i m; i ){ cw[i] 0; for (int j 1; j r; j ) cw[i] abs(matrix[q[j]][i] - matrix[q[j - 1]][i]); } for (int i 0; i m; i ) for (int j i 1; j m; j ){ rw[i][j] 0; for (int k 0; k r; k ) rw[i][j] abs(matrix[q[k]][i] - matrix[q[k]][j]); } for (int i 0; i m; i ){ f[i][1] cw[i]; for (int j 2; j c; j ){ f[i][j] INF; for (int k 0; k i; k ) f[i][j] min(f[i][j], f[k][j - 1] cw[i] rw[k][i]); } res min(res, f[i][c]); } } cout res endl; return 0; }