题解 P7239 【3D Cube】
破壁人罗辑
·
·
题解
题意简述
求出一个各行各列元素之和最少的矩阵，使得每一行的最大值和每一列的最大值满足给定的要求、矩阵中有且只有给定的位置元素非零且每一行和每一列的序列前后各加上一个 0 后最多只有一个峰。
解题思路
### 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;
}
```