题解 P7239 【3D Cube】

题意简述

求出一个各行各列元素之和最少的矩阵，使得每一行的最大值和每一列的最大值满足给定的要求、矩阵中有且只有给定的位置元素非零且每一行和每一列的序列前后各加上一个

0

后最多只有一个峰。

解题思路

n\times m\leq25

，数据范围很小，并且可以发现

n^m+m^n<10^5

，能够直接

O(n^m+m^n)

暴力枚举每一行的最大值位置和每一列的最大值位置，然后再用

O(mn)

求出答案并判断是否合法，再和当前最优解比较和的大小，如果更小就替换当前最优解。时间复杂度

O(mn(n^m+m^n))

，估算起来小于

10^6

，能过。

AC 代码

CPP

#include<bits/stdc++.h>
using namespace std;
int mt[25][25],ans[25][25],dp[25][25],x[25],y[25],n,m,top[26];
long long tot;
int check(int i,int j){//求解元素(i,j)的值
	if(dp[i][j]||!mt[i][j])return dp[i][j];
	dp[i][j]=1;//防止无限递归
	return dp[i][j]=max(mt[i][j],
		max(i<top[n+j]?i?check(i-1,j):0:i==n-1?0:check(i+1,j),
			j<top[i]?j?check(i,j-1):0:j==m-1?0:check(i,j+1)));
}
void dfs(){
	while(1){
		for(int h=n+m-1;top[h]>=(h<n?m:n);top[--h]++){
			if(!h)return;//如果枚举完成就return
			top[h]=0;
		}
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)dp[i][j]=0;
		long long tots=0;
		for(int i=0;i<n;i++){
			if(x[i]&&!mt[i][top[i]])goto nxt;
      //不满足条件，跳到下一个状态
			dp[i][top[i]]=x[i];
		}
		for(int j=0;j<m;j++){
			if(y[j]&&!mt[top[n+j]][j])goto nxt;
      //不满足条件，跳到下一个状态
			dp[top[n+j]][j]=max(dp[top[n+j]][j],y[j]);
		}
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(mt[i][j])
			if((tots+=check(i,j))>=tot||dp[i][j]>x[i]||dp[i][j]>y[j])goto nxt;
            //不是最优解或不满足条件，跳到下一个状态
		for(int i=1;i<n-1&&tots<1e17;i++)for(int j=0;j<m;j++)
			if(dp[i-1][j]>dp[i][j]&&dp[i+1][j]>dp[i][j])goto nxt;
            //不满足条件，跳到下一个状态
		for(int i=0;i<n&&tots<1e17;i++)for(int j=1;j<m-1;j++)
			if(dp[i][j-1]>dp[i][j]&&dp[i][j+1]>dp[i][j])goto nxt;
            //不满足条件，跳到下一个状态
		for(int i=0;i<n;i++)for(int j=0;j<m;j++)ans[i][j]=dp[i][j];
		tot=tots;
		nxt:
		top[n+m-1]++;//枚举下一个状态
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%d",x+i);
	for(int i=0;i<m;i++)scanf("%d",y+i);
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&mt[i][j]);

//初步判断是否条件
	for(int i=0;i<n;i++){
		bool has=mt[i][0];
		for(int j=1;j<m;j++){
			if(has&&j+1<m&&mt[i][j+1]&&!mt[i][j]){puts("-1");return 0;}
			has=has||mt[i][j];
		}
		if(has!=(x[i]!=0)){puts("-1");return 0;}
	}
	for(int j=0;j<m;j++){
		bool has=mt[j][0];
		for(int i=0;i<n;i++){
			if(has&&i+1<n&&mt[i+1][j]&&!mt[i][j]){puts("-1");return 0;}
			has=has||mt[i][j];
		}
		if(has!=(y[j]!=0)){puts("-1");return 0;}
	}

	tot=1e18;dfs();
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)
      if(mt[i][j]!=(ans[i][j]!=0)){puts("-1");return 0;}//判断ans是否满足条件
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)printf("%d ",ans[i][j]);
		putchar('\n');
	}
	return 0;
}

题解 P7239 【3D Cube】

文章操作

题意简述

解题思路

AC 代码

相关推荐

评论

题解 P7239 【3D Cube】