【正经题解】子矩阵

边搜索边 $dp$ ，枚举出选那些行，然后算出每列之间的分数 $w$ ，两列之间的分数 $v$ 。
就可以开始 $dp$ 了， $f$ [ $i$ ][ $j$ ]表示已经选了 $i$ 列，最后一列是 $j$ 的最小分数。
状态转移方程： $f$ [ $i$ ][ $j$ ] $=min$ ( $f$ [ $i-1$ ][ $k$ [ $+w$ [ $j$ ] $+v$ [ $j$ ][ $k$ ])。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define min(a,b) (a<b?a:b)
int n,m,r,c;
int a[18][18],f[18][18];
//f[i][j]表示已经选了i列，最后一列是j的最小分数
int w[18],v[18][18],rec[18];
//每列之间的分数w，两列之间的分数v
int ans=1<<30;
void dps()
{
    memset(f,127,sizeof(f));
    memset(w,0,sizeof(w));
    memset(v,0,sizeof(v)); 
    //f[i][j]=min(f[i-1][k]+w[j]+v[j][k],f[i][j])
    int i,j,k;
    for (i=1; i<=m; ++i)
    {
        for (j=1; j<r; ++j)
        {
            w[i]=w[i]+abs(a[rec[j]][i]-a[rec[j+1]][i]);
        }
        //cout<<w[i]<<"w"<<endl;
    }
    for (i=1; i<=m; ++i) 
    {
        for (j=i+1; j<=m; ++j) 
        {
            for (k=1; k<=r; ++k)
            {
                v[i][j]=v[i][j]+abs(a[rec[k]][i]-a[rec[k]][j]);
            }
            //cout<<v[i][j]<<"v";
        }
    }
    f[0][0]=0; //(0,0)=0
    for (i=1; i<=c; ++i) //选了I列
    {
        for (j=i; j<=m; ++j) //最后一列为J
        {
            for (k=0; k<j; ++k) //枚举上一次选的列数
            {
                f[i][j]=min(f[i-1][k]+w[j]+v[k][j],f[i][j]);
            } 
        } 
    } 
    for (i=c; i<=m; ++i)
    {
        ans=min(ans,f[c][i]);
    }
}
void dfs(int x,int y)
{
    if(y>r)
    {
        dps();
        return;
    }
    if (x>n) return;
    dfs(x+1,y); //这一列不选 ,Next one
    rec[y]=x; //记录x的值在rec【y】中体现 
    dfs(x+1,y+1); //选！ 
}
int main()
{
    int i,j;
    cin>>n>>m>>r>>c;
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=m; ++j)
        {
            scanf("%d",&a[i][j]);
        }
    }
    dfs(1,1);
    cout<<ans;    
}