题目大意就是要你找到一个矩阵的最大的全0子矩阵的面积，复杂度是O(n^2)的。
我在去年12月份在CODEVS上做过一道叫做"玉蟾宫"的题，一模一样……
当时照着题解打了一发只有90分，还以为是字符串读入的问题。结果刚刚翻了一下之前的代码。
竟然能有90分.jpg
既然是n^2，就一定有什么奇淫巧技。
首先有几个结论(现在做题怎么都先找结论)：
1.答案矩阵不可能往上下左右拓展(显然)。
2.我们只枚举某一行作为最后一行是可行的(显然)。
3.答案一定在一个以(i,j)点到当前第j列能扩展到的最高的点(i',j)的高为(i-i'+1)的最宽的矩阵上。
即：确定一个点(i,j)，能往上走就往上走，走到不能走之后往两边扩展，扩展不了就计算，答案是正确的。
证明的话，既然有结论1，则必定在最后一行有一个(i,j)只能扩展到这么多。然后往两边扩展，答案就出来了。
其实就有了一种很好写也可以过的O(n^2logn)的做法。
枚举点(i,j)，二分找到上界，二分找到左边，二分找到右边。
用一个二维前缀和维护一下1的个数就可以实现O(1)的check了。这几个二分是并的，复杂度单独计算，所以是O(n^2logn)，貌似也有人写。
但是UVALive好像有多组数据，也不知道能不能过去(只怕是不能的)。
然后来考虑怎么在O(n^2)的时间内解决它。
找到上界这个东西很简单，直接SB地DP(递推)就可以了。重点是维护左右扩展。
其实这个也很简单，从左往右枚举j，维护一下当前节点左边第一个1的位置，然后和上一行的取Max。右边类似，反过来即可。
这样就实现了O(n^2)的计算，可以通过此题了。
注意在不为0时的左边右边的赋值。因为它对下面不会有约束，要把左界设成0，右界设成m+1(就是不会影响的意思)。
思路还是很喵喵喵的。
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <cstring> #include <queue> #include <complex> #include <stack> #define LL long long int #define dob double #define FILE "3029" using namespace std; const int N = 1010; int n,m,map[N][N],up[N][N],le[N][N],ri[N][N],Ans; int gi(){ int x=0;char ch=getchar(); while(ch>'9' || ch<'0')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar(); return x; } int gec(){ char ch=getchar(); while(ch!='F' && ch!='R')ch=getchar(); return ch=='F' ? 0:1; } inline void solve(){ Ans=0;n=gi(),m=gi(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) map[i][j]=gec(); for(int i=1;i<=n;++i){ int ls=0,rs=m+1; for(int j=1;j<=m;++j) if(map[i][j]==1){le[i][j]=0;ls=j;up[i][j]=0;} else if(i==1){up[i][j]=1,le[i][j]=ls+1;} else up[i][j]=up[i-1][j]+1,le[i][j]=max(le[i-1][j],ls+1); for(int j=m;j>=1;--j) if(map[i][j]==1){ri[i][j]=m;rs=j;} else{ if(i==1){ri[i][j]=rs-1;} else ri[i][j]=min(ri[i-1][j],rs-1); Ans=max(Ans,up[i][j]*(ri[i][j]-le[i][j]+1)); } } printf("%d ",Ans*3); } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); int Case=gi(); for(int i=1;i<=Case;++i) solve(); }