???????目录

题目?

题解

题目?

给出如下定义：

1. 子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。

   例如，下面左图中选取第?2?、?4?行和第?2?、?4?、?5?列交叉位置的元素得到一个?2×3?的子矩阵如右图所示。

1. 相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。

1. 矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。

本题任务：给定一个?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

样例输入1

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

样例输出1

6

样例输入2

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

样例输出2

16

题解：

知识点：动态规划+二进制枚举子集

分析：?

首先这道题目我们可以很容易想到暴力， 如果剪枝得当是可以 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++输出一下数据。

代码：

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
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;
}