题解：P2258 [NOIP2014 普及组] 子矩阵

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
const int N=20;
int min=2147482647;
int map[N][N];
int qu[N];
int n,m,r,c;
int xx[N],yy[N][N];
int f[N][N];
void dp()
{
	memset(xx,0,sizeof(xx));
	memset(yy,0,sizeof(yy));
	memset(f,127,sizeof(f));
	for(int i=1;i<=m;i++)
	for(int j=2;j<=r;j++)
	xx[i]+=abs(map[qu[j]][i]-map[qu[j-1]][i]);
	
	for(int i=1;i<=m;i++)
	for(int j=i+1;j<=m;j++)
	for(int k=1;k<=r;k++)
	yy[i][j]+=abs( map[qu[k]][i]-map[qu[k]][j]);
	
	for(int i=1;i<=m;i++)	f[i][0]=0,f[i][1]=xx[i];
	
	for(int i=1;i<=m;i++)
	for(int j=2;j<=c;j++)
	{
		for(int k=1;k<i;k++)
		f[i][j]=std::min(f[i][j],f[k][j-1]+yy[k][i]+xx[i]);
	}
	for(int i=1;i<=m;i++)
	min=std::min(min,f[i][c]);
}
void dfs(int i,int step)
{
	if(step==r+1)	
	{
		dp();
		return;
	}
	if(n-i<r-step)	return;
	for( ;i<=n;i++)	
	qu[step]=i,dfs(i+1,step+1);
}
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",&map[i][j]);
	dfs(1,1);
	printf("%d\n",min);
	return 0;
}