将一个\(n*m\)的01矩阵沿着列切几刀，拆成若干个\(n*w_i\)大小的矩阵，你可以重新任意排列它们来拼成一个新的\(n*m\)的01矩阵，使得矩阵中最大的全0矩形面积最大。

Solution

这题关键在于\(n*m\leq 10^5\)，即矩阵大小不超过\(10^5\)。一种直觉是平衡规划，即分\(n\leq \sqrt{10^5}\)和\(m\leq \sqrt{10^5}\)两种情况分别设计算法。

\(n\leq \sqrt{10^5}\)

枚举最终全0矩形的上下边界\(l,r\)，然后对每个小矩阵分类。若小矩阵内第\(l\)行至第\(r\)行全部为0，分为I类，，否则分为II类。

最后肯定是把I类的矩阵放在中间，两边放II类的矩阵来凑成一个全0矩形，那么，我们需要计算I类矩阵宽度之和，以及II类矩阵在左边最多几列为全0，右边最多几列为全0。需要注意的是，左右不能用II类矩阵中的同一个，所以我们还要记录一下次大值，不能用最大值时用次大值替换。

时间复杂度\(O(n^2m)=O(10^5n)\)，\(n\)是根号级别的，显然不会超时。

\(m\leq 10^5\)

这时就不能直接枚举矩形的上下边界了，我们可以用另一种方法枚举上下边界：

记录矩形中每个点\((i,j)\)往上第一个\(1\)的行号（记作\(up[i][j]\)）。枚举矩形中的每个点\((i,j)\)，将\(up[i][j]\)作为上边界，\(i\)作为下边界。（替换了原来暴力枚举的上边界\(r\)，下边界\(l\)）

剩下的过程套用上面的即可，时间复杂度\(O(nm^2)=O(10^5m)\)，\(m\)是根号级别的，也不会超时。

至此，问题解决。

Code #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100007; int T; int s,n,m,ans,w[N],st[N],en[N],sum[N],a[N],up[N]; int id(int x,int y){ if(x<1||y<1)return 0; return (y-1)*n+x; } int get(int x1,int x2,int y1,int y2){ return sum[id(x2,y2)]-sum[id(x1-1,y2)]-sum[id(x2,y1-1)]+sum[id(x1-1,y1-1)]; } void calc(int l,int r){ for(int i=1;i<=s;++i)for(int j=st[i],ret=0;j<=en[i];++j){ if(get(l,r,j,j)==0)++ret; else ret=0; ans=max(ans,(r-l+1)*ret); } int L[2][2],R[2][2],mid=0; memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); for(int i=1;i<=s;++i){ int mxl=0,mxr=0; for(int j=st[i];j<=en[i];++j)if(get(l,r,j,j)==0)++mxl;else break; for(int j=en[i];j>=st[i];--j)if(get(l,r,j,j)==0)++mxr;else break; if(mxl==w[i])mid+=w[i]; else{ if(mxl>L[0][0])L[0][0]=mxl,L[0][1]=i; else if(mxl>L[1][0])L[1][0]=mxl,L[1][1]=i; if(mxr>R[0][0])R[0][0]=mxr,R[0][1]=i; else if(mxr>R[1][0])R[1][0]=mxr,R[1][1]=i; } } for(int p=0;p<2;++p)for(int q=0;q<2;++q)if(L[p][1]!=R[q][1])ans=max(ans,(r-l+1)*(mid+L[p][0]+R[q][0])); ans=max(ans,(r-l+1)*(mid+L[0][0])); ans=max(ans,(r-l+1)*(mid+R[0][0])); } int main(){ scanf("%d",&T); while(T--){ m=ans=0; scanf("%d%d",&s,&n); memset(w,0,sizeof(w)); memset(st,0,sizeof(st)); memset(en,0,sizeof(en)); memset(sum,0,sizeof(sum)); memset(a,0,sizeof(a)); memset(up,0,sizeof(up)); for(int i=1;i<=s;++i){ scanf("%d",&w[i]); st[i]=m+1; for(int j=1;j<=n;++j)for(int k=1;k<=w[i];++k){ char c;scanf(" %c",&c); a[id(j,m+k)]=c-'0'; } m+=w[i],en[i]=m; } for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[id(i,j)]=sum[id(i-1,j)]+sum[id(i,j-1)]-sum[id(i-1,j-1)]+a[id(i,j)]; for(int j=1;j<=m;++j) for(int i=1,lst=0;i<=n+1;++i) if(i>n||a[id(i,j)]){ for(int k=lst+1;k<=i-1;++k)up[id(k,j)]=i-1; lst=i; } if(n<m)for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)calc(i,j); else for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)calc(i,up[id(i,j)]); printf("%d\n",ans); } return 0; }

【JZOJ3672】【JSOI2014】拼图(puzzle)