再不救我我就要死了!QWQWQ(二郎神流泪)
查看原帖
再不救我我就要死了!QWQWQ(二郎神流泪)
658786
STUDENT00楼主2022/12/29 16:25

求助啊!

#include<bits/stdc++.h>
#define lowbit(x) x&-x
#define N 20
using namespace std;
int n,m,r,c,a[N][N],f1[N][N],f2[N],dp[N][N],ans=1e9;
vector<int> v;
int check(int x){
	int s=0;
	while(x){
		s++;
		x-=lowbit(x);
	}
	return s==c;
}
int main(){
	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]);
	for(int p=0;p<(1<<m);p++){
		if(check(p)){
			memset(f1,0,sizeof(f1));
			memset(f2,0,sizeof(f2));
			memset(dp,63,sizeof(dp));
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					for(int k=1;k<=m;k++) f1[i][j]+=abs(a[i][k]-a[j][k]); 
				}
			}
			for(int i=1;i<=n;i++){
				int last=0;
				for(int j=1;j<=m;j++){
					if(p&(1<<j-1)){if(last) f2[i]+=abs(a[i][j]-a[i][last]);last=j;}
				}
			}
			for(int i=1;i<=n;i++){
				dp[i][1]=f2[i];
				for(int j=2;j<=r;j++){
					for(int k=1;k<i;k++) dp[i][j]=min(dp[i][j],dp[k][j-1]+f1[i][j]+f2[i]);
					if(j==r) ans=min(ans,dp[i][j]);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}
2022/12/29 16:25
加载中...