【2014NOIP普及组】T4:子矩阵 试题解析

//样例代码  枚举+线性DP
#include
using namespace std;
const int N=20;
int w[N][N];//原始数据数组
int f[N][N];//状态数组f[i][j]从前i行中选了j列 且第i行被选
int rw[N][N],cw[N];
int q[N];//储存所选出的行
int n,m,r,c;
int get_count(int x){//统计x的二进制位上有几个1
	int res=0;
	for(int i=0;i
		if((x>>i)&1) res++;
	return res;
}
int main()
{
	cin>>n>>m>>r>>c;
	for(int i=0;i
		for(int j=0;j>w[i][j];
	int res=1e8;
	for(int i=0;i<(1<//从n个当中选r个
		if(get_count(i)==r){//用二进制位为1来暴力枚举选择的r行
			for(int j=0,k=0;j
				if((i>>j) & 1) q[k++]=j;//储存所选出的行
			for(int j=0;j
				cw[j]=0;
				for(int k=1;k//计算j行的矩阵的分值
					cw[j]+=abs(w[q[k]][j]-w[q[k-1]][j]);
			}
			for(int j=0;j
				for(int k=j+