难度：提高+/省选-

题目描述

        给出如下定义:
        子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。
        例如，下面左图中选取第2，4行和第2，4，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
的其中一个2×3的子矩阵是
4     7     4
8     6     9

        相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
        矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。
        本题任务:给定一个n行m列的正整数矩阵，请你从这个矩阵中选出一个r行c列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。

输入输出格式

输入格式:

        第一行包含用空格隔开的四个整数n，m，r，c意义如问题描述中所述，每两个整数之间用一个空格隔开。
        接下来的n行，每行包含m个用空格隔开的整数，用来表示问题描述中那个n行m列的矩阵。

输出格式:

        一个整数，表示满足题目描述的子矩阵的最小分值。

输入输出样例

Sample input#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

Sample output#1

6

Sample input#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

Sample output#2

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 ≤ n ≤ 12，1 ≤ m ≤ 12矩阵中的每个元素1≤aij≤20;
        对于100%的数据，1 ≤ n ≤ 16，1 ≤ m ≤ 16，矩阵中的每个元素1≤aij≤1000，1≤r≤n，1≤c≤m。

题解

        题目考察动态规划和DFS，实际上本题考察这两种方法的结合。由于涉及到行和列的全排，直接进行DP无法写出状态转移方程。
        容易发现给定矩阵的型很小(不大于16)，在这种情况下用指数级时间复杂度的DFS枚举出所有的行排列，在这个基础上对列进行DP。这时DFS时间复杂度为$O(C_n^r)$，DP时间复杂度为$O(n^3)$。总时间复杂度即为$O(C_n^r*n^3)$。
        对于一种行的枚举情况，令f(x，y)表示从前x列中取y列可以获得的最小绝对值之和(第x列必须在其中且x≥y)，那么有状态转移方程:

        这里S1(k，x)表示第k列与第x列对应行元素差的绝对值之和，S2(x)表示第x列对应行之间差的绝对值之和。这两个都可以在DP前暴力求出。这样就会使原本$O(n^2)$的DP升为$O(n^3)$，但由于较小的数据规模，这仍然是一种可行的解法。
        f(x，x)直接暴力求出即可。最后在其中找到f(x，c)最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cmath>
#include <cstring>

int op[20][20];
int vr[17][17][17];
int vc[17][17][17];
int vis[17] = {0}, que[17] = {0};
int dp[17][17];
int t[17];
int ans = (int) 1e9;
int n, m, r, c;
using namespace std;

int fun(int x) {
    if (t[x] != -1)return t[x];
    t[x] = 0;
    for (int i = 0; i < r - 1; i++)t[x] += vc[x][que[i]][que[i + 1]];
    return t[x];
}

int DP(int x, int y) {
    if (dp[x][y] != -1)return dp[x][y];
    if (x == 1)return fun(y);
    if (x == y) {
        dp[x][y] = 0;
        for (int i = 1; i <= x; i++)dp[x][y] += fun(i);
        for (int i = 0; i < r; i++) {
            for (int j = 1; j < x; j++)dp[x][y] += vr[que[i]][j][j + 1];
        }
        return dp[x][y];
    }
    int temp = (int) 1e9;
    for (int i = x - 1; i < y; i++) {
        int q = DP(x - 1, i) + fun(y);
        for (int j = 0; j < r; j++) {
            q += vr[que[j]][i][y];
        }
        temp = min(temp, q);
    }
    return dp[x][y] = temp;
}

void DFS(int step, int begin) {
    if (step == r) {
        memset(dp, -1, sizeof(dp));
        memset(t, -1, sizeof(t));
        for (int i = c; i <= m; i++)ans = min(ans, DP(c, i));
        return;
    }
    for (int i = begin; i <= n; i++) {
        if (vis[i])continue;
        vis[i] = 1;
        que[step] = i;
        DFS(step + 1, i);
        vis[i] = 0;
    }
}

int main() {
    cin >> n >> m >> r >> c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)cin >> op[i][j];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            for (int z = j + 1; z <= m; z++)vr[i][j][z] = vr[i][z][j] = abs(op[i][j] - op[i][z]);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j < n; j++) {
            for (int z = j + 1; z <= n; z++)vc[i][j][z] = vc[i][z][j] = abs(op[j][i] - op[z][i]);
        }
    }
    DFS(0, 1);
    cout << ans;
    return 0;
}