链接：https://ac.nowcoder.com/acm/problem/16503
来源：牛客网
题目描述
给出如下定义：
1.子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。
例如，下面左图中选取第 2 、 4 行和第 2 、 4 、 5 列交叉位置的元素得到一个 2 x 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 x 3 的子矩阵是
| 4 | 7 | 4 |
| 8 | 6 | 9 |
2.相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。
3.矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。
本题任务：给定一个 n 行 m 列的正整数矩阵，请你从这个矩阵中选出一个 r 行 c 列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。
输入描述:
输入第一行包含用空格隔开的四个整数 n,m,r,c ，意义如问题描述中所述，每两个整数之间用一个空格隔开。
接下来的 n 行，每行包含 m 个用空格隔开的整数，用来表示问题描述中那个 n 行 m 列的矩阵。
输出描述:
一个整数，表示满足题目描述的子矩阵的最小分值。
示例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。
解题思路：枚举选出行的情况，然后对列进行DP就可以了。dp【i】【j】为选了j列，并且右边第一列为第i列的值。那么dp【i】【j】=min（dp【k】【j】+加入第i列对行之间的绝对值的影响+加入i列对列之间的绝对值的影响）。
至于这两个“影响”怎么求看代码中的“init”吧。
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn=20; typedef long long ll; int a[maxn][maxn]; int n,m,r,c; int vis[maxn]; int dp[maxn][maxn]; vector<int> vec; int hang[maxn],lie[maxn][maxn]; int ans; void init(){ memset(hang,0,sizeof(hang)); memset(lie,0,sizeof(lie)); for(int i=1;i<=n;i++){ if(vis[i]==1) vec.push_back(i); } int len=vec.size(); for(int i=1;i<=m;i++){ for(int j=0;j<len-1;j++){ hang[i]+=abs(a[vec[j]][i]-a[vec[j+1]][i]); } } for(int i=1;i<=m;i++){ for(int j=i+1;j<=m;j++){ for(int k=0;k<len;k++){ lie[i][j]+=abs(a[vec[k]][i]-a[vec[k]][j]); } lie[j][i]=lie[i][j]; } } vec.clear(); } void DP(){ for(int i=1;i<=m;i++){ dp[i][c]=inf; for(int j=1;j<=i;j++){ if(j==1)dp[i][j]=hang[i]; else if(i==j){ dp[i][j]=dp[i-1][j-1]+hang[i]+lie[i-1][i]; } else{ dp[i][j]=inf; for(int k=j-1;k<i;k++){ dp[i][j]=min(dp[i][j],dp[k][j-1]+hang[i]+lie[k][i]); } } } ans=min(ans,dp[i][c]); } } void solve(int be,int cnt){ if(cnt==r){ init(); DP(); return ; } if(be>n){ return ; } vis[be]=1; solve(be+1,cnt+1); vis[be]=0; solve(be+1,cnt); return ; } int main(){ scanf("%d%d%d%d",&n,&m,&r,&c); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } ans=inf; solve(1,0); printf("%d ",ans); return 0; }