随手一写就冲进了最优解的第一页?

本来以为是dp, 但是经过仔细分析...这不就是二进制 + 单调栈么?

然后想正方形的情况...emm..好像正方形一定是最大矩形的子矩阵吧!

听说此题dp也可行?

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef pair
          
            P;const int MAXN = 2e3 + 20;const int INF = 0x3f3f3f3f;inline int read(){ int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x;}int N, M;int sum[2][MAXN];bool map[2][MAXN];P ans(1, 1);struct Sta{ stack
           
 sta; void init(){ pushin(0); while(!sta.empty()) sta.pop(); return ; } void pushin(int h){ if(sta.empty() || sta.top().first < h) { sta.push(P(h, 1)); return ; } int len = 0, hei = INF; while(!sta.empty() && sta.top().first > h) { P p = sta.top(); sta.pop(); len += p.second; hei = min(hei, p.first); ans.first = max(ans.first, len * p.first); ans.second = max(ans.second, min(len, hei) * min(len, hei)); } sta.push(P(h, len + 1)); return; }}S;int main(){ cin>>N>>M; int d = 0; for(int i = 1; i <= N; i++){ d ^= 1; if(i == 1) { for(int j = 1; j <= M; j++) sum[d][j] = 1, map[d][j] = read(); continue; } for(int j = 1; j <= M; j++){ map[d][j] = read(); sum[d][j] = (map[d ^ 1][j] ^ map[d][j]) ? sum[d ^ 1][j] + 1 : 1; if(j - 1 && map[d][j] ^ map[d][j - 1]) S.pushin(sum[d][j]); else S.init(), S.pushin(sum[d][j]); } S.init(); } cout<
            
             <