记录编号	457425	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014PJ]子矩阵	最终得分	100
用户昵称	nfy_2002	是否通过	通过
代码语言	C++	运行时间	0.266 s
提交时间	2017-10-07 23:03:54	内存使用	0.32 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define RG register
#define IL inline
#define pi acos(-1.0)
#define ll long long 
using namespace std;

int n,m,r,c;
int a[20][20],L[20],dp[20][20],p[20],f[20][20];
int minn=999999999;

void DP(){
	memset(p,0,sizeof(p));
	memset(f,0,sizeof(f));
	memset(dp,55,sizeof(dp));
	for(RG int i=1;i<=m;i++)
		for(RG int j=1;j<r;j++)
			p[i]+=abs(a[L[j]][i]-a[L[j+1]][i]);//预处理竖着的贡献
  for(RG int i=1;i<=m;i++)
		for(RG int j=1;j<i;j++)
			for(RG int k=1;k<=r;k++)
				f[i][j]+=abs(a[L[k]][i]-a[L[k]][j]);//预处理横着的贡献
	for(RG int i=1;i<=m;i++)
		dp[1][i]=p[i];//已经选了1列，且第i列必选的最小代价
	for(RG int i=1;i<=m;i++)
		for(RG int j=1;j<i;j++){
			RG int z=min(c-1,j);
			for(RG int k=1;k<=z;k++)
				dp[k+1][i]=min(dp[k+1][i],dp[k][j]+p[i]+f[i][j]);
		}
	for(RG int i=1;i<=m;i++)
		minn=min(dp[c][i],minn);
}

void dfs(int pre,int f){
	if(f==r+1){
		DP();
		return;
	}
	for(int i=pre+1;i<=n;i++){
		L[f]=i;
		dfs(i,f+1);
	}
}

int main(){
  freopen("submatrix.in","r",stdin);
	freopen("submatrix.out","w",stdout);
  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(0,1);
  printf("%d",minn);
	return 0;
}