这道题题意很简单，意思是在n行中选r行，在m列中选c列，这样行和列交叉的点就形成了一个r行c列的矩阵。问在所有这样的矩阵中，上矩阵中相邻每两数之差的绝对值和的最小值是多少。
贴一个样例的说明图：
看到这题第一反应就是暴力！在n行中取r个进行组合，在从m列中取c个进行组合，然后计算出所得矩阵的值，再求最小值即可。那么这样的时间复杂度是多少呢？本人粗略算了一下，最差大概是C(16,8)^2=165,636,900 很明显超时了......所以考虑优化：
问题来了，如何优化？枚举行，然后贪心列吗？但只要细心思考一下，就会发现贪心是不可行的。那么怎么办？
贪心不行，自然考虑是动态规划啦！能不能动态规划首先要考虑的是有没有后效性。如果我们枚举行(hang)，那么动态规划要解决的问题就是在m列中选c列，使组成的子矩阵值最大。设 f[i][j] 表示在 i 列中选了（过去式） j 列（第 i 列必须选）的最大值，这我们需预处理一些值：lc[i]（原谅我英文不好lie‘cha）表示第 i 列中的（每个数之差的绝对值） 之和，hc[i][j] （hang‘cha）表示第 i 列的每个数与 第 j 列每个数之差的绝对值之和。那么就有：
f[i][j] = max( f[i][j] , f[k][j-1] + hc[i][k] + lc[i] )
初始化：f[1][1] = lc[1]
注意边界：f[i][1] = lc[i] and (i==j) f[i][j] = f[i-1][j-1] + hc[i][j-1] + lc[i]
注：认真思考就很容易懂得（这是一个线性DP!）
那我们再来算算时间复杂度：最差情况大概是 C(16,8) * m^3 大概是52,715,520（emmm......卡卡常就卡过啦）
下面你懂得（不负责任地贴代码......）：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=20; 4 const int INF=2147483647; 5 int a[maxn][maxn]; 6 int n,m,r,c,ans; 7 int vish[maxn],hc[maxn][maxn],lc[maxn],f[maxn][maxn]; 8 void Memset() //预处理 9 { 10 for(int i=1; i<=m; i++) 11 lc[i]=0; 12 for(int i=1; i<=m; i++) 13 for(int j=1; j<=m; j++) 14 hc[i][j]=0; 15 for(int i=1; i<=m; i++) 16 for(int j=1; j<r; j++) 17 lc[i]+=abs(a[vish[j]][i]-a[vish[j+1]][i]); 18 for(int i=2; i<=m; i++) 19 for(int j=1; j<i; j++) 20 for(int k=1; k<=r; k++) 21 hc[i][j]+=abs(a[vish[k]][i]-a[vish[k]][j]); 22 } 23 void makeans() 24 { 25 f[1][1]=lc[1]; 26 for(int i=2; i<=m; i++) 27 { 28 for(int j=1; j<=(i<c?i:c); j++) 29 { 30 f[i][j]=INF; 31 if(j==1) f[i][j]=lc[i]; //边界 32 else if(i==j) f[i][j]=f[i-1][j-1]+hc[i][j-1]+lc[i]; //边界*2 33 else 34 { 35 for(int k=i-1; k>=j-1; k--) 36 f[i][j]=min(f[i][j],f[k][j-1]+hc[i][k]+lc[i]); //状态转移方程 37 } 38 if(j==c) ans=min(ans,f[i][c]); //记录最小值 39 } 40 } 41 return ; 42 } 43 void dfs(int k,int j) //回溯法求组合数 44 { 45 if(k==r+1) {Memset();makeans();return ;} 46 for(int i=j+1; i<=n; i++) 47 { 48 vish[k]=i; 49 dfs(k+1,i); 50 } 51 } 52 int main() 53 { 54 ans=INF; 55 scanf("%d%d%d%d",&n,&m,&r,&c); 56 for(int i=1; i<=n; i++) 57 for(int j=1; j<=m; j++) 58 scanf("%d",&a[i][j]); 59 dfs(1,0); 60 printf("%d",ans); 61 return 0; 62 }
原文：https://www.cnblogs.com/GDOI2018/p/9732757.html