记录编号	324001	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014PJ]子矩阵	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.657 s
提交时间	2016-10-17 17:11:30	内存使用	0.30 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 17
#define INF 1<<29
using namespace std;
int dt[maxn]={0};
int n,m,r,c;
int a[maxn][maxn]={0};
int val[maxn]={0};
int dis[maxn][maxn]={0};
int d[maxn][maxn]={0};
int ans=INF;
void pre(){
	memset(val,0,sizeof(val));
	memset(dis,0,sizeof(dis));
	for (int i=1;i<=r;i++){
//		printf("%d ",dt[i]);
	}
//	printf(":");
	for (int i=1;i<=m;i++){
		for (int p=2;p<=r;p++){
			int j=dt[p];
			val[i]+=abs(a[j][i]-a[dt[p-1]][i]);
		}
//		printf("	%d",val[i]);
	}
	for (int i=1;i<=m;i++){
		for (int j=i+1;j<=m;j++){
			for (int p=1;p<=r;p++){
				int k=dt[p];
				dis[i][j]+=abs(a[k][i]-a[k][j]);	
			}
			dis[i][j]+=val[j];
		}
	}
}
void DP(){
	memset(d,0,sizeof(d));
	pre();
	for (int i=1;i<=m;i++){
		d[i][1]=val[i];
		for (int j=2;j<=c;j++){
			d[i][j]=INF;
			for (int k=1;k<i;k++){
				d[i][j]=min(d[k][j-1]+dis[k][i],d[i][j]);
			}
		}
	}
	for (int i=1;i<=m;i++){
		ans=min(ans,d[i][c]);
	}
}
void dfs(int x,int t){
	if (t==r) {
		DP();
//		printf("\n");
		return;
	}
	if (x>n) return;
	dfs(x+1,t);
	dt[++t]=x;
	dfs(x+1,t);
}
void read(){
	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]);
		}
	}
}
int main(){
	freopen("submatrix.in","r",stdin);
	freopen("submatrix.out","w",stdout);
	read();
	dfs(1,0); 
	printf("%d",ans);
	return 0;
}
/*
7 7 3 3
7 7 7 6 2 10 5
5 8 8 2 1 6 2
2 9 5 5 6 1 7
7 9 3 6 1 7 8
1 9 1 4 7 8 8
10 5 9 1 1 8 10
1 3 1 5 4 8 6
*/