# 最大子矩阵(SOJ 3329)

SOJ 3329: Maximum Submatrix II http://acm.scu.edu.cn/soj/problem.action?id=3329

Problem: Given a \$0-1\$ matrix, find the maximum submatrix which contains only 0s and output the number of 0s in it.

Technique:

(1) Dynamic Programming

Denote \$dp[i][j], 1\le i\le n, 1\le j\le m\$ as the maximum number of sequential 0s ended at \$[i,j]\$, then the number of 0s in the maximum submatrix ended at \$[i,j]\$ is

\$\max_{i‘‘\le i‘\le i}\min_{i‘\le k\le i}dp[k][j]*(i-k+1)\$.

The time complexity is \$O(m^{2}n)\$.

Code:

```#include<iostream>
using namespace std;
int mat[105][105];
int dp[105][105];
int main()
{
int n,m;
int T;
int i,j,k;
int temp;
int minTep;
int ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(j=0;j<=m;j++)
{
mat[0][j]=1;
dp[0][j]=0;
}
for(i=0;i<=n;i++)
{
mat[i][0]=1;
dp[i][0]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&mat[i][j]);
dp[i][j]=mat[i][j] ? 0 : dp[i][j-1]+1;
}
ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
temp=0;
minTep=m+1;
for(k=i;k>0;k--)
{
if(dp[k][j])
{
minTep=dp[k][j]<minTep ? dp[k][j] : minTep;
temp=temp>minTep*(i-k+1) ? temp : minTep*(i-k+1);
}
else
break;
}
ans=temp>ans ? temp : ans;
}
printf("%d\n",ans);
}

return 0;
}```
View Code

(2) Monotonic Stack

Note that given a list of \$dp[k][j], i‘\le k\le i\$, the number of 0s in the submatrix is the minimum of \$dp[k][j]\$ times the length of the list, which is similar to SOJ 3085 (see here). Specifically, we can maintain an increasing stack.

0 0 0 \$dp[i‘][j]\$

0 0 \$\dots\$

0 \$dp[i-1][j]\$

0 0 0 0 \$dp[i][j]\$

Code:

```#include<iostream>
#include<stack>
using namespace std;
struct node
{
int num;
int no;
int prevNo;
};
int mat[1005][1005];
int main()
{
int n,m;
int i,j;
stack<node>s;
int temp;
int ans;
node x;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(j=1;j<=m;j++)
{
mat[0][j]=0;
mat[n+1][j]=0;
}
for(i=1;i<=n;i++)
mat[i][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&temp);
mat[i][j]=temp ? 0 : mat[i][j-1]+1;
}
ans=0;
for(j=1;j<=m;j++)
for(i=0;i<=n+1;i++)
{
while(!s.empty() && mat[i][j]<s.top().num)
{
temp=s.top().num*(i-1-s.top().prevNo);
ans=temp>ans ? temp : ans;
s.pop();
}
x.num=mat[i][j];
x.no=i;
x.prevNo=s.size() ? s.top().no : 0;
s.push(x);
}
while(!s.empty())
s.pop();
printf("%d\n",ans);
}
return 0;
}```
View Code

(0)
(0)

0条