简答题
偏难
#23633
子矩阵 【问题描述】 给出如下定义: 1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。 例…
子矩阵
【问题描述】
给出如下定义:
1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
例如,下面左图中选取第 2、4 行和第 2、4、5 列交叉位置的元素得到一个 2*3 的子矩阵如右图所示。

2. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
3. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。
本题任务:给定一个 n 行 m 列的正整数矩阵,请你从这个矩阵中选出一个 r 行 c 列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。
【输入】
输入文件名为 submatrix.in。
第一行包含用空格隔开的四个整数 n,m,r,c,意义如问题᧿述中所述,每两个整数之间用一个空格隔开。
接下来的 n 行,每行包含 m 个用空格隔开的整数,用来表示问题᧿述中那个 n 行 m 列的矩阵。
【输出】
输出文件名为 submatrix.out。
输出共 1 行,包含 1 个整数,表示满足题目描述的子矩阵的最小分值。
【输入输出样例 1】

【输入输出样例 1 说明】
该矩阵中分值最小的 2 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行与第 1 列、第 3 列、

【输入输出样例 2】

【输入输出样例 2 说明】
该矩阵中分值最小的 3 行 3 列的子矩阵由原矩阵的第 4 行、第 5 行、第 6 行与第 2 列、第 6 列、第 7 列交叉位置的元素组成,选取的分值最小的子矩阵为
【数据说明】

答案与解析
正确答案:<p style="text-align: left;">#include<bits/stdc++.h></p><p><br style="text-align: left;"/></p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N = 20;</p><p style="text-align: left;">int n, m, r, c;</p><p style="text-align: left;">int num[N][N], ch[N], gs = 1;</p><p style="text-align: left;">int lc[N], hc[N][N];</p><p style="text-align: left;">int f[N][N];</p><p><br style="text-align: left;"/></p><p style="text-align: left;">/*</p><p style="text-align: left;">具体思路:</p><p style="text-align: left;">首先想到暴力方法</p><p style="text-align: left;">枚举每个rc大小的矩阵,然后计算差值和,但复杂度过高</p><p style="text-align: left;">需要优化:</p><p style="text-align: left;">首先枚举n行中的r行</p><p style="text-align: left;">利用dfs()枚举每种可能,当dfs()进行到已经不能完成r行时停止</p><p style="text-align: left;">预处理选出来的r行每一列之间的行与行的差值和即lc[i]</p><p style="text-align: left;">在预处理c列中任意两列之间的差值和即hc[i][j] 第i列和第j列的差值和</p><p style="text-align: left;">利用线性dp处理即可</p><p style="text-align: left;">f[i][j]表示前i列中选j列的最小值(选第j列)</p><p style="text-align: left;">f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k])</p><p style="text-align: left;">*/</p><p style="text-align: left;">void Init()</p><p style="text-align: left;">{</p><p style="text-align: left;"> for(int i = 1; i <= m; i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> lc[i] = 0;</p><p style="text-align: left;"> for(int j = 1; j < r; j++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> lc[i] += abs(num[ch[j]][i] - num[ch[j + 1]][i]);//</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> for(int i = 2; i <= m; i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> for(int j = 1; j < i; j++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> hc[i][j] = 0; //第i列减第j列的中r行的差值差值</p><p style="text-align: left;"> for(int k = 1; k <= r; k++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> hc[i][j] += abs(num[ch[k]][i] - num[ch[k]][j]);</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p style="text-align: left;">int minn = 2e9;</p><p style="text-align: left;">int cmin;</p><p style="text-align: left;">void dp()</p><p style="text-align: left;">{</p><p style="text-align: left;"> for(int i = 1; i <= m; i++) //前i行</p><p style="text-align: left;"> {</p><p style="text-align: left;"> cmin = min(i, c);</p><p style="text-align: left;"> for(int j = 1; j <= cmin; j++)//选j行</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(j == 1)</p><p style="text-align: left;"> f[i][j] = lc[i];</p><p style="text-align: left;"> else</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(i == j)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> f[i][j] = f[i - 1][j - 1] + lc[i] + hc[i][j - 1];</p><p style="text-align: left;"> }</p><p style="text-align: left;"> else</p><p style="text-align: left;"> {</p><p style="text-align: left;"> f[i][j] = 2e8;</p><p style="text-align: left;"> for(int k = j - 1; k < i; k++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> f[i][j] = min(f[i][j], f[k][j - 1] + lc[i] + hc[i][k]);</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(j == c) minn = min(minn, f[i][c]);//前i列选c列</p><p style="text-align: left;"> }</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p><br style="text-align: left;"/></p><p style="text-align: left;">void dfs(int node)</p><p style="text-align: left;">{</p><p style="text-align: left;"> if(node > n)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> Init();</p><p style="text-align: left;"> dp();</p><p style="text-align: left;"> return;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> if(r - gs + 1 == n - node + 1)//已经取地行数还没取得行数 优化剪枝</p><p style="text-align: left;"> {</p><p style="text-align: left;"> ch[gs ++] = node;</p><p style="text-align: left;"> dfs(node + 1);</p><p style="text-align: left;"> ch[gs --] = 0;</p><p style="text-align: left;"> return;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> dfs(node + 1);</p><p style="text-align: left;"> if(gs <= r)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> ch[gs ++] = node;</p><p style="text-align: left;"> dfs(node + 1);</p><p style="text-align: left;"> ch[gs --];</p><p style="text-align: left;"> }</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"> cout << 2<<20 << e</p><p style="text-align: left;"> scanf("%d%d%d%d", &n, &m, &r, &c);</p><p style="text-align: left;"> for(int i = 1; i <= n; i++)</p><p style="text-align: left;"> for(int j = 1; j <= m; j++)</p><p style="text-align: left;"> scanf("%d", &num[i][j]);</p><p style="text-align: left;"> dfs(1);</p><p style="text-align: left;"> printf("%d", minn);</p><p style="text-align: left;"> return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。