题解 | #Call to your teacher#

这道题有点像工程题的dp版本
特点就是比较繁琐
首先先枚举选取出来的行，列也行
然后定义状态f[i][j],表示前i列中选出j列时的最小分差和
然后状态转移即可
如果看不懂，说明基础不行，回去多补补题

#include<bits/stdc++.h>
using namespace std;
vector< vector<int> >gen(vector <vector<int> >matri,int row,int k){
	int n=matri.size(),m=matri[0].size();
	vector< vector<int> >res(row,vector<int>(m));
	int inx=0;
	for(int i=0;i<n;i++){
		if((k>>i)&1){
			for(int j=0;j<m;j++){
				res[inx][j]=matri[i][j];
			}
			inx++;
		}
	}
	return res;
}
bool check(int x,int r){
	int cnt=0;
	while(x){
		if(x%2)cnt++;
		x/=2;
	}
	return (cnt==r);      
}
int solve(vector< vector<int> >matri,int c){

	int n=matri.size(),m=matri[0].size();
	int f[m+1][m+1];
	for(int i=0;i<m+1;i++){
		for(int j=0;j<m+1;j++){
			f[i][j]=1e9;
		}
	}
	int res=1e9;
	for(int i=0;i<m;i++){
		for(int j=1;j<=min(c,i+1);j++){
			
			int tmp=0;
			for(int r=0;r<n-1;r++)tmp+=abs(matri[r][i]-matri[r+1][i]);
//			cout<<tmp<<endl;
			if(j==1){
				f[i][j]=tmp;
			}
			else {
				for(int k=0;k<i;k++){
					int tmp2=0;
					for(int r=0;r<n;r++)tmp2+=abs(matri[r][i]-matri[r][k]);
					f[i][j]=min(f[i][j],f[k][j-1]+tmp+tmp2);
				}
			}
			
			if(j==c)res=min(res,f[i][j]);
		}
	}
	return res;
}
int main(){
//	freopen("1.txt","r",stdin);
	int n,m,r,c;
	cin>>n>>m>>r>>c;
	
	vector< vector<int> >matri(n,vector<int>(m));
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>matri[i][j];
		}
	}
	int res=1e9;
	for(int k=0;k<1<<n;k++){
		if(!check(k,r)) continue;
		vector< vector<int> >subm(r,vector<int>(c));
		subm=gen(matri,r,k);
		res=min(res,solve(subm,c));
//		cout<<res<<endl;
	}
	cout<<res;
	
}