记录编号	324135	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014PJ]子矩阵	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.514 s
提交时间	2016-10-17 20:07:07	内存使用	0.28 MiB

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define file(x) "submatrix."#x
using std::min;
const int MAXN=20;
int a[MAXN][MAXN],r,c,pr[MAXN],pc[MAXN],n,m,ans=1<<30,w[MAXN][MAXN],w2[MAXN],f[MAXN][MAXN];
void dp(){
	memset(f,0x3f,sizeof(f));
	memset(w,0,sizeof(w));
	memset(w2,0,sizeof(w2));
	for(int i=1;i<=m;i++) {
		for(int j=1;j<r;j++) {
			int nr=pr[j];
			w2[i]+=abs(a[nr][i]-a[pr[j+1]][i]);
		}
		f[i][1]=w2[i];
	}
	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++){
		for(int k=1;k<=r;k++){
			int nr=pr[k];
			w[i][j]+=abs(a[nr][i]-a[nr][j]);
		}
	}
	for(int i=1;i<=m;i++) for(int j=1;j<=c;j++){
		for(int k=1;k<i;k++) {
			f[i][j]=min(f[i][j],f[k][j-1]+w[k][i]+w2[i]);
		}
	}
	int tmp=f[m][c];
	for(int i=1;i<=m;i++) tmp=min(tmp,f[i][c]);
	ans=min(ans,tmp);
}
void dfs1(int now,int cnt){
	if(cnt==r+1){
		dp();
		return; 
	}
	for(int i=now+1;i<=n;i++) pr[cnt]=i,dfs1(i,cnt+1);
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(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]);
	dfs1(0,1);
	printf("%d",ans);
}