DFS枚举行，用DP处理枚举之后的列。
枚举用数组MJ【i】记录被枚举的第i行对应原下标。每层DFS修改数组对应位置中的值。
DP【i】【j】表示前i列选j列且选中最后一列是j时的最小值。
初始化DP数组时，DP【i】【0】显然是0，DP【i】【1】则是只选中该列时的值，即该行的各个元素上下之间产生的分数。
动规时，选定被更新列i和遍历列j之后，算一次两列左右之间产生的分数，记为SUM。则：

dp[i][k]=min(dp[i][k],dp[j][k-1]+sum+dp[i][1]);

即，选中k-1列时的分数+新加入列与最后列的左右分数+新加入列上下分数。

#include <iostream>
#include <cstring>

using namespace std;

int n,m,a,b;
int ma[20][20];
int dp[20][20]={0};
int mj[20]={0};
int ans=2e9;

int abs(int x)
{
    if(x<0)
    {
        return -x;
    }
    else
    {
        return x;
    }
}

void work()
{
    memset(dp,62,sizeof(dp));
    int i,j,k,sum;
    for(i=0;i<m;i++)
    {
        dp[i][0]=0;
        dp[i][1]=0;
        for(j=1;j<a;j++)
        {
            dp[i][1]+=abs(ma[mj[j]][i]-ma[mj[j-1]][i]);//上下分
        }
    }
    for(i=1;i<m;i++)
    {
        for(j=0;j<i;j++)
        {
            sum=0;
            for(k=0;k<a;k++)
            {
                sum+=abs(ma[mj[k]][i]-ma[mj[k]][j]);//两列左右分
            }
            for(k=2;k<=b;k++)
            {
                dp[i][k]=min(dp[i][k],dp[j][k-1]+sum+dp[i][1]);
            }
        }
    }
    for(i=0;i<m;i++)
    {
        ans=min(ans,dp[i][b]);
    }
}

void dfs(int x)
{
    if(x==a)
    {
        work();
    }
    else if(mj[x]<n)
    {
        for(;mj[x]<n;mj[x]++)
        {
            mj[x+1]=mj[x]+1;
            dfs(x+1);
        }
    }
}

int main()
{
    cin>>n>>m>>a>>b;
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            cin>>ma[i][j];
        }
    }
    dfs(0);
    cout<<ans<<endl;
    return 0;
}

开篇先声明一点：这是**C++**的题解（貌似直接交C也不会CE），Pascal请看下面那篇！
好吧，先祝大家W不A，T和M不LE，C和R不E！
上面都不是重点，我们正式来讲一讲这道题。
看到题目，相信大家有认真用脑子想都能想出一个暴力的方法——DFS。
深度优先搜索作为暴力算法中最重要的一个搜索算法，如果加上适当的剪枝，那么可能用非正解的方式~~以999 ms的时间~~AC。
但是，很明显，这样的数据范围是无论如何不可能完全用深度优先搜索AC的（不过听说90分可以），所以遇到这种问题只能用一种叫做动（biàn）态规划的算法。
动态规划，DP，一般要找出一个类似于递推方程式（后面不讲了，各位OIer大神都知道）。那么这题怎么做呢？我们先来看代码。

#include<cstdio>
#include<cstring>
#define reg register
const int N=17,inf=2147483647;
int n,m,r,c,p[N][N],v[N],f[N],res=inf,t[N],t1[N][N];
inline void init()
{
scanf("%d%d%d%d",&n,&m,&r,&c);
for(reg int i=1;i<=n;i++)
for(reg int j=1;j<=m;j++)
scanf("%d",&p[i][j]);
}
inline int abs(reg int i)
{
return i<0?-i:i;
}
inline int min(reg int i,reg int j)
{
return i<j?i:j;
}
inline int DP()
{
memset(t,0,sizeof(t));
memset(t1,0,sizeof(t1));
for(reg int i=1;i<=m;i++)
for(reg int j=1;j<v[0];j++)
t[i]+=abs(p[v[j]][i]-p[v[j+1]][i]);
for(reg int i=1;i<m;i++)
for(reg int j=i+1;j<=m;j++)
for(reg int k=1;k<=v[0];k++)
t1[i][j]+=abs(p[v[k]][i]-p[v[k]][j]);
for(reg int i=1;i<=m;i++)
f[i]=t[i];
for(reg int i=2;i<=c;i++)
for(reg int j=m;j>=i;j--)
{
f[j]=inf;
for(reg int k=j-1;k>=i-1;k--)
f[j]=min(f[j],f[k]+t1[k][j]);
f[j]+=t[j];
}
reg int ans=inf;
for(reg int i=c;i<=m;i++)
ans=min(ans,f[i]);
return ans;
}
inline void DFS(reg int i,reg int dep)
{
if(dep==r)
{
res=min(res,DP());
return;
}
for(reg int j=i;j<=n-r+dep+1;j++)
{
v[++v[0]]=j;
DFS(j+1,dep+1);
v[v[0]--]=0;
}
}
inline void work()
{
DFS(1,0);
printf("%d\n",res);
}
int main()
{
init();
work();
return 0;
}

先不必管变量加速器register和函数加速器inline，大家看出来程序使用了DFS+DP（事实证明这对组合挺高效的）。
我们需要考虑到首先可以枚举一行中的某些列，先使用DFS，并加上一点剪枝。此时，在枚举出一种情况时，使用DP确定出可行解。然后再考虑一些其他东西，找出最优解。
大概就这些重要内容，其实这道题在DFS和DP中的细节也不少，容易出错，这里不再一一阐述，大家自己可以依照代码消化一下。希望这篇题解对大家有所帮助，谢谢。

var w,r,minn,i,j,n,m:longint;
c:array[0..16] of longint;
a,b,s,f:array[0..16,0..16] of longint;
function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;
procedure dp;
var i,sum,j,k:longint;
begin
fillchar(s,sizeof(s),0);
for i:=1 to m do
for j:=1 to i do
begin
for k:=1 to r do s[i,j]:=s[i,j]+abs(b[k,i]-b[k,j]);
for k:=1 to r-1 do s[i,j]:=s[i,j]+abs(b[k,i]-b[k+1,i]);
end;
fillchar(f,sizeof(f),12);
for i:=1 to m do f[1,i]:=s[i,i];
for i:=2 to w do
for j:=i to m-w+i do
for k:=i-1 to j-1 do
f[i,j]:=min(f[i,j],f[i-1,k]+s[j,k]);
for i:=w to m do
minn:=min(minn,f[w,i])
end;
procedure dfsr(x,s:longint);
var i:longint;
begin
if s=r then
begin
dp;
exit;
end;
if x=n+1 then exit;
for i:=0 to 1 do
begin
if i=1 then b[s+1]:=a[x];
dfsr(x+1,s+i);
end;
end;
begin
assign(input,'submatrix.in');
reset(input);
assign(output,'submatrix.out');
rewrite(output);
readln(n,m,r,w);
for i:=1 to n do
for j:=1 to m do read(a[i,j]);
minn:=maxlongint;
dfsr(1,0);
writeln(minn);
close(input);
close(output);
end.

var mtx,f:array[0..20,0..20] of longint;
    hi,lc:array[0..20] of longint;
    i,j,n,m,r,c,ans:longint;
    
    function min(a,b:longint):longint;
    begin if a>b then exit(b);exit(a);end;
    
    procedure jsh;
    var i,j:longint;                            //static 行差
    begin
        fillchar(lc,sizeof(lc),0);
        for i:=1 to m do
            for j:=2 to r do begin
                inc(lc[i],abs(mtx[i,hi[j]]-mtx[i,hi[pred(j)]]));
                //writeln(mtx[i,hi[j]],'-',mtx[i,hi[pred(j)]],' ',i);
            end;
    end;
    
    
    function jsl(a,b:longint):longint;
    var i:longint;                              //dymanic compute
    begin
        jsl:=0;
        for i:=1 to r do
            inc(jsl,abs(mtx[a,hi[i]]-mtx[b,hi[i]]))
    end;
    
    
    procedure work;
    var i,j,k:longint;                          //core code,uses DP
    begin
        filldword(f,sizeof(f)>>2,maxlongint>>2);
        jsh;
        for i:=1 to m do begin
            f[1,i]:=lc[i];end;
        for i:=2 to c do
            for j:=i to m do
                for k:=i-1 to j-1 do begin
                    f[i,j]:=min(f[i,j],f[pred(i),k]+jsl(k,j)+lc[j]);
                    
                end;
        //for i:=1 to r do write(hi[i],' ');writeln(lc[hi[r]],' ',hi[r]);
        for i:=1 to m do ans:=min(ans,f[c,i]);
    end;
    
    
    procedure search(k:longint);
    var i:longint;                              //search hang
    begin
        if (k>r)and(hi[r]<=n) then begin
            work;exit;
        end;
        for i:=succ(hi[pred(k)]) to n do begin
            hi[k]:=i;search(succ(k));
        end;
    end;


begin
    //assign(input,'submatrix.in');assign(output,'submatrix.out');
    //reset(input);rewrite(output);
    ans:=maxlongint;
    fillchar(hi,sizeof(hi),false);
    read(n,m,r,c);
    for i:=1 to n do for j:=1 to m do read(mtx[j,i]);
    hi[0]:=0;search(1);
    writeln(ans);
    //close(input);close(output);
end.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,r,c;
int a[20][20];
int ls[20],hs[20][20];
int list[20];
int ans=0x7fffffff;
int f[20][20];
inline void ldfs(int x,int last,int nowc,int nowsum){
    int i,j;
    for(i=0;i<m;++i)
        for(j=0;j<=c;++j)
            f[i][j]=1E9;
    for(i=0;i<m;++i)f[0][0]=0,f[i][1]=ls[i];
    int k;
    for(i=1;i<m;++i)
        for(j=2;j<=c;++j){
            for(k=0;k<i;++k)f[i][j]=min(f[i][j],f[k][j-1]+hs[k][i]);
            f[i][j]+=ls[i];
        }
    for(i=0;i<m;++i)ans=min(ans,f[i][c]);
}
inline void hdfs(int x,int now){
    if(n-x<now)return;
    if(x==n){
        int i,j;
        memset(ls,0,sizeof(ls));
        for(i=m;i--;)
            for(j=r;--j;)
                ls[i]+=abs(a[list[j]][i]-a[list[j-1]][i]);
        int k;
        memset(hs,0,sizeof(hs));
        for(i=0;i<m;++i)
            for(j=i+1;j<m;++j)
                for(k=r;k--;)
                    hs[i][j]+=abs(a[list[k]][i]-a[list[k]][j]);
        ldfs(0,m-1,c,0);
        return;
    }
    hdfs(x+1,now);
    if(now){
        list[--now]=x;
        hdfs(x+1,now);
    }
}
int main(){
    freopen("submatrix.in","r",stdin);
    freopen("submatrix.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&r,&c);
    int i,j;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            scanf("%d",a[i]+j);
    hdfs(0,r);
    printf("%d\n",ans);
}

//var n,m,r,c,i,j,ans:longint; a:array[0..16,0..16]of longint; b:array[0..17]of longint;

procedure doit;
var i,j,k,min:longint;  zc:array[0..16]of longint; t,w,hc:array[0..16,0..16]of longint;
begin
   fillchar(zc,sizeof(zc),0);
   fillchar(hc,sizeof(hc),0);
   fillchar(t,sizeof(t),0);

   for i:=1 to r do
      for j:=1 to m do w[i,j]:=a[b[i],j];
   for i:=1 to m-1 do
      for j:=i+1 to m do
         for k:=1 to r do
            hc[i,j]:=abs(w[k,i]-w[k,j])+hc[i,j];
   for j:=1 to m do
      for i:=1 to r-1 do zc[j]:=abs(w[i,j]-w[i+1,j])+zc[j];

   for k:=1 to m do t[1,k]:=zc[k];
   for k:=2 to c do
      for j:=k to m do begin
        min:=maxlongint;
        for i:=k-1 to j-1 do
          if min>t[k-1,i]+zc[j]+hc[i,j] then min:=t[k-1,i]+zc[j]+hc[i,j];
        t[k,j]:=min; end;
   for i:=c to m do if ans>t[c,i] then ans:=t[c,i];
end;

procedure search_hang(k,p:longint);
var i:longint;
begin
   if k=r+1 then begin doit end
   else
     for i:=p+1 to n do
     begin
         b[k]:=i;
         search_hang(k+1,i);
     end;
end;

begin

readln(n,m,r,c);
for i:=1 to n do begin
for j:=1 to m do read(a[i,j]);
readln; end;
ans:=maxlongint div 2;
search_hang(1,0);
writeln(ans);
end.

最优化减枝or直接dp

才发现近些年普及组的题目还是很有深度的嘛QwQ，这个题是搜索+dp，先枚举行，再dp列，楼下很详细了。补个复杂度分析吧：
搜索加可行性剪枝后，总次数为O(C(n,a)) = O(n!/a!/(n-a)!)。
不难发现a = n-a时取最大，为：O(C(n,n/2));
动态规划的复杂度为O(n^3)，总的复杂度为：O(C(n,n/2)*n^3)
a = n时取最小，为Ω(n^3)

这题直接动归比较复杂，可以用搜索+动归解决
由于在确定了选择哪些行之后，动归变得简单易行，所以先搜索枚举行的排列，然后基于这些排列进行动归。f[i][j] 表示 目前选了 i 列，最后选的那一列是第 j 列 时的最小分数。

f[i][j] = f[i-1][k] + score[j] + score2[k]j

其中 score 及 score2 是预处理过的。score[j] 是根据目前的 行排列 计算出的第 j 列上下相邻元素的差的绝对值之和。score2[k][j] 是根据目前的 行排列 计算出的第 k 列与第 j 列 左右相邻元素的差的绝对值之和

#include <stdio.h>
#include <stdlib.h>

#define INF 1000000000

int n, m, row, col;
int answer = INF;

int matrix[20][20];
int scoreCol[20]; //scoreCol[i] = score of column i
int score2Col[20][20]; //score2Col[i][j] = additional score when column i & column j be combined
int f[20][20];

int MIN(int a, int b){
return a<b ? a:b;
}
int DP(int rowStatus){
int i, j, k, fMin = INF;
int rows[20];

j = 0;
for(i=0; i<n; i++){
if((rowStatus>>i) & 1)
rows[j++] = i;
}
for(i=0; i<m; i++){
scoreCol[i] = 0;
for(j=1; j<row; j++)
scoreCol[i] += abs(matrix[rows[j]][i] - matrix[rows[j-1]][i]);

for(j=i+1; j<m; j++){
score2Col[i][j] = 0;
for(k=0; k<row; k++)
score2Col[i][j] += abs(matrix[rows[k]][j] - matrix[rows[k]][i]);
}
}

for(i=0; i<m; i++){
for(j=0; j<m; j++)
f[i][j] = INF;
}
for(j=0; j<m; j++)
f[1][j] = scoreCol[j];

for(i=2; i<=col; i++){ //i columns have been selected
for(j=i-1; j<m; j++){ //current column
for(k=0; k<j; k++) //previous column
f[i][j] = MIN(f[i][j], f[i-1][k] + scoreCol[j] + score2Col[k][j]);
}
}

for(j=0; j<m; j++)
fMin = MIN(fMin, f[col][j]);

return fMin;
}
void solve(int depth, int status, int rowLeft){
if(depth >= n){
if(rowLeft == 0)
answer = MIN(answer, DP(status));
}else{
if(rowLeft > 0)
solve(depth+1, (status<<1)|1, rowLeft-1);
if(rowLeft <= n-depth)
solve(depth+1, status<<1, rowLeft);
}
}
int main(){
int i, j;
scanf("%d %d %d %d", &n, &m, &row, &col);
for(i=0; i<n; i++){
for(j=0; j<m; j++)
scanf("%d", &matrix[i][j]);
}
solve(0, 0, row);
printf("%d\n", answer);
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 20;
const int INF = 100000000;

int used[MAXN], a[MAXN][MAXN], f[MAXN][MAXN], shu[MAXN];
int n, m, r, c, sum = 0, ans = INF;

int cal_abs(int s, int b){
int tot = 0;
for(int i=1; i<=n; i++)
if(used[i])
tot += abs(a[i][s]-a[i][b]);
return tot;
}

void DP(){
for(int i=1; i<=m; i++){
for(int j=1; j<=c; j++)
f[i][j] = INF;
}
memset(shu, 0, sizeof(shu));
for(int i=1; i<=m; i++)
for(int u=1; u<=n; u++)
if(used[u]){
int qiao = a[u][i];
for(int j=u+1; j<=n; j++)
if(used[j]){
shu[i] += abs(qiao-a[j][i]);
qiao = a[j][i];

}
f[i][1] = shu[i];
break;
}
for(int i=2; i<=c; i++)
for(int j=i; j<=m; j++)
for(int u=i-1; u<j; u++)
f[j][i] = min(f[j][i], f[u][i-1]+cal_abs(j, u)+shu[j]);
for(int i=1; i<=m; i++)
ans = min(ans, f[i][c]);
}

void dfs(int deep){
if(sum == r){
DP();
return;
}
if(deep > n)
return;
dfs(deep+1);
used[deep] = 1;
sum++;
dfs(deep+1);
used[deep] = 0;
sum--;
}

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]);
dfs(1);
printf("%d", ans);
return 0;
}
DFS + DP~~~

var
n,m,r,c,ans,i,j:longint;
a,f,e:array[0..16,0..16] of longint;
y,d:array[0..16] of longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end;

procedure dfs(t:longint);
var
i,j,k:longint;
begin
if t>c then
begin
for i:=1 to n do
for j:=1 to r do
f[i,j]:=1000000000;
for i:=1 to n do
begin
d[i]:=0;
for j:=1 to c-1 do
d[i]:=d[i]+abs(a[i,y[j]]-a[i,y[j+1]]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
begin
e[i,j]:=0;
for k:=1 to c do
e[i,j]:=e[i,j]+abs(a[i,y[k]]-a[j,y[k]]);
end;
for i:=1 to n do
f[i,1]:=d[i];
for i:=2 to n do
for j:=2 to min(r,i) do
for k:=j-1 to i-1 do
f[i,j]:=min(f[i,j],f[k,j-1]+d[i]+e[k,i]);
for i:=r to n do
if ans>f[i,r] then
ans:=f[i,r];
exit;
end;
for i:=y[t-1]+1 to m do
begin
y[t]:=i;
dfs(t+1);
end;
end;

begin
readln(n,m,r,c);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
ans:=1000000000;
y[0]:=0;
dfs(1);
writeln(ans);
end.

编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
74 lines compiled, 0.0 sec , 29568 bytes code, 1628 bytes data
测试数据 #0: Accepted, time = 15 ms, mem = 448 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 448 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 448 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 448 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 448 KiB, score = 10
测试数据 #5: Accepted, time = 218 ms, mem = 452 KiB, score = 10
测试数据 #6: Accepted, time = 187 ms, mem = 452 KiB, score = 10
测试数据 #7: Accepted, time = 218 ms, mem = 452 KiB, score = 10
测试数据 #8: Accepted, time = 203 ms, mem = 452 KiB, score = 10
测试数据 #9: Accepted, time = 203 ms, mem = 452 KiB, score = 10
Accepted, time = 1059 ms, mem = 452 KiB, score = 100
代码
program exercise(input,output);
type arr=array[0..17,0..17]of longint;
var n,m,r,c,ans:longint;
map:arr;
a,b:arr;
procedure readin;
var i,j:longint;
begin
readln(n,m,r,c);
ans:=maxlongint;
for i:=1 to n do
begin
for j:=1 to m do
read(map[i,j]);
readln;
end;
end;
function min(x,y:longint):longint;
begin
if x<y then
exit(x);
exit(y);
end;
procedure count(x,y,w:longint;f:arr);
var p:arr;
i,j,k,l:longint;
begin
fillchar(p,sizeof(p),0);
if x>r then
for i:=w to x do
begin
for k:=1 to x do
begin
if k<i then
for l:=1 to y do
p[k,l]:=f[k,l];
if k>i then
for l:=1 to y do
p[k-1,l]:=f[k,l];
end;
count(x-1,y,i,p);
end;
if x=r then
begin
fillchar(a,sizeof(a),127);
fillchar(b,sizeof(b),0);
for i:=1 to y do
for j:=i to y do
begin
for k:=1 to x do
begin
if k<x then
b[i,j]:=b[i,j]+abs(f[k,j]-f[k+1,j]);
b[i,j]:=b[i,j]+abs(f[k,i]-f[k,j]);
end;
b[j,i]:=b[i,j];
end;
for i:=1 to c do
for j:=i to y do
if i=1 then
a[i,j]:=b[j,j]
else
for k:=i-1 to j-1 do
a[i,j]:=min(a[i,j],a[i-1,k]+b[k,j]);
l:=maxlongint;
for i:=c to y do
l:=min(l,a[c,i]);
ans:=min(ans,l);
end;
end;
begin
readin;
count(n,m,1,map);
writeln(ans);
end.

郁闷。果然是DP，简直了。。。
我一开始看这个题目跟NOIP提高组初赛试卷的程序填空子矩阵好像，就以为是DP。但是还是蛋疼的失算写了DFS。啧。果然不是这么简单的小玩意哦。DP呢。。。

题解：看到这道题。很容易就想到DFS。这是很正常的想法。因此我们枚举所有行和列的可能性。然后计算总和。找到最小即可。时间复杂度很大。只能完成50的数据。

正确的写法应该是半DFS半DP或者可以直接DP（感觉有点难想了- -）我这里就说半DFS半DP的思路

前面和原先一样，找到所有行的可能性。

但是我们就不找列了。

例如样例1.我们找到了1和2列。那么割出如下矩阵
9 3 3 3 9
9 4 8 7 4

建立一个数组f进行动态规划。f[i,j]中i表示第i次分割。j表示分割的位置。有点类似VIJOS上普及组的乘积最大。
首先边界条件我们发现假如你选了第1列。那么这一列上的所有上下产生的值我们都是要考虑进来的。因此提前把每一列上下的值算好。放入f【1，j】这里j表示第几列。那么边界条件就有了

状态转移是。每一次的分割。比如我这是第2次分割。那么我只要考虑2-后面的割法。可以保证不重复。原理跟1 2 3 4 5个数问你22组合有几种你数法一个道理1 2 ，1 3， 1 4 15 2 3 2 4 2 5这样数下来对吧？

那么给出状态转移f[i,j]:=min(f[i,j],(f[i-1,k]+sum+f[1,j]));

sum等于这一列跟前上一次你选的这一列左右产生的值。

啊= =好吧。发现不太好讲。大家可以看我代码具体领会或者自己写写画画。或者网上看看别人题解。恕我比较蠢- -
###pascal code
program P1914;
uses math;
var n,m,r,c,i,j,k,minn,sum:longint;
data,f:array[1..16,1..16] of longint;
h,a:array[1..16] of longint;
procedure ans;
var i,j,k,l:longint;
begin
fillchar(f,sizeof(f),$7f); sum:=0;
for i:=1 to 16 do f[1,i]:=0;
for i:=1 to m do
for j:=1 to r-1 do
f[1,i]:=f[1,i]+abs(data[h[j],i]-data[h[j+1],i]);

for i:=2 to c do
for j:=i to m do
for k:=i-1 to j-1 do
begin
sum:=0;
for l:=1 to r do sum:=sum+abs(data[h[l],j]-data[h[l],k]);
if f[i,j]>2000000 then
f[i,j]:=f[i-1,k]+sum+f[1,j]
else
f[i,j]:=min(f[i,j],(f[i-1,k]+sum+f[1,j]));
end;

for i:=c to m do
if f[c,i]<minn then
minn:=f[c,i];
end;

procedure search1(x,y:longint);
var i:longint;
begin
if x=r+1 then begin ans; exit end;
for i:=y to n do
begin
h[x]:=i;
search1(x+1,i+1);
end;
end;

begin//main
read(n,m); read(r,c); minn:=maxlongint;
fillchar(data,sizeof(data),0); fillchar(h,sizeof(h),0);
for i:=1 to n do
for j:=1 to m do
read(data[i,j]);
search1(1,1);
write(minn);
end.

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int mp[20][20];
int dp[20000][20][20];
int n,m,r,c;
int sta[20000];
int v[20000][20][20];
int vv[20000][20];
int sc;

int abs(int a)
{
return a>0?a:-a;
}

int min(int a,int b)
{
return a<b?a:b;
}

int main()
{
scanf("%d%d%d%d",&n,&m,&r,&c);
for (int i=1;i<=n;i++)
for (int t=0;t<m;t++)
scanf("%d",&mp[i][t]);
memset(dp,-1,sizeof(dp));
memset(v,0,sizeof(v));
memset(vv,0,sizeof(vv));
int mm=(1<<m)-1;
sc=0;
for (int i=0;i<=mm;i++) //寻找可用的列的选取情况
{
int cnt=0;
for (int t=0;t<m;t++)
{
int x=(1<<t);
if (x&i)
cnt++;
}
if (cnt==c) //找到一种
{
sta[sc]=i;
dp[sc][0][0]=0; //新状态下第0行选取0行的最优解为0，表示可用
for (int k=1;k<=n;k++)
{
int pre=-1;
for (int j=0;j<m;j++) //记录这种情况下每行的值
{
int x=(1<<j);
if (x&i)
{
if (pre!=-1)
vv[sc][k]+=abs(mp[k][j]-mp[k][pre]);
pre=j;
}
}
for (int t=k+1;t<=n;t++) //记录这种情况下行间的值
{
int ans=0;
for (int j=0;j<m;j++)
{
int x=(1<<j);
if (x&i)
{
ans+=abs(mp[t][j]-mp[k][j]);
}
}
v[sc][k][t]=ans;
}
}
sc++;
}
}
int ans=99999999;
for (int i=1;i<=n;i++) //对于每行结尾的
{
for (int t=0;t<sc;t++) //状态编号为t的
{
for (int k=0;k<i;k++) //跟第k行组合的
{
for (int j=0;j<=k&&j<r;j++) //形成的矩阵行数为j的子矩阵，获得其最优解
{
if (dp[t][i][j+1]==-1)
dp[t][i][j+1]=dp[t][k][j]+v[t][k][i]+vv[t][i];
else
dp[t][i][j+1]=min(dp[t][i][j+1],dp[t][k][j]+v[t][k][i]+vv[t][i]);
if (j+1==r)
ans=min(ans,dp[t][i][j+1]);
}
}
}
}
printf("%d\n",ans);
}

Pascal Code
var
n,m,r,c,ans,i,j:longint;
a,f,e:array[0..16,0..16] of longint;
y,d:array[0..16] of longint;

function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end;

procedure dfs(t:longint);
var
i,j,k:longint;
begin
if t>c then
begin
for i:=1 to n do
for j:=1 to r do
f[i,j]:=1000000000;
for i:=1 to n do
begin
d[i]:=0;
for j:=1 to c-1 do
d[i]:=d[i]+abs(a[i,y[j]]-a[i,y[j+1]]);
end;
for i:=1 to n-1 do
for j:=i+1 to n do
begin
e[i,j]:=0;
for k:=1 to c do
e[i,j]:=e[i,j]+abs(a[i,y[k]]-a[j,y[k]]);
end;
for i:=1 to n do
f[i,1]:=d[i];
for i:=2 to n do
for j:=2 to min(r,i) do
for k:=j-1 to i-1 do
f[i,j]:=min(f[i,j],f[k,j-1]+d[i]+e[k,i]);
for i:=r to n do
if ans>f[i,r] then
ans:=f[i,r];
exit;
end;
for i:=y[t-1]+1 to m do
begin
y[t]:=i;
dfs(t+1);
end;
end;

begin
readln(n,m,r,c);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
ans:=1000000000;
y[0]:=0;
dfs(1);
writeln(ans);
end.