简答题 偏难
#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&lt;bits/stdc++.h&gt;</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 &lt;= 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 &lt; 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 &lt;= m; i++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        for(int j = 1; j &lt; 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 &lt;= 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 &lt;= 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 &lt;= 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 &lt; 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 &gt; 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 &lt;= 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 &lt;&lt; 2&lt;&lt;20 &lt;&lt; e</p><p style="text-align: left;">    scanf("%d%d%d%d", &amp;n, &amp;m, &amp;r, &amp;c);</p><p style="text-align: left;">    for(int i = 1; i &lt;= n; i++)</p><p style="text-align: left;">        for(int j = 1; j &lt;= m; j++)</p><p style="text-align: left;">            scanf("%d", &amp;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>
这道题暂未补解析。