http://poj.org/problem?id=3494
http://zhuanlan.zhihu.com/qinchao/19873823

做法一：单调栈
http://poj.org/problem?id=2559
https://www.shuizilong.com/house/archives/ad-infinitum-math-programming-contest-september14

//}/* .................................................................................................................................. */

const int N = int(2e3) + 9;

int A[N][N], h[N], l[N], r[N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
#endif


    while (~scanf("%d %d", &n, &m)){
        REP_2_1(i, j, n, m) RD(A[i][j]);

        int z = 0; h[0] = 0, h[m+1] = 0; REP_1(i, n){
            REP_1(j, m) h[j] = (A[i][j] == 1 ? h[j] + 1 : 0);

            stack<int> s; s.push(0); REP_1(i, m){
                if (h[i]){
                    while (h[i] <= h[s.top()]) s.pop();
                    l[i] = s.top()+1;
                }
                else{
                    CLR(s);
                }
                s.push(i);
            }

            CLR(s); s.push(m+1); DWN_1(i, m, 1){
                if (h[i]){
                    while (h[i] <= h[s.top()]) s.pop();
                    r[i] = s.top();
                }
                else{
                    CLR(s);
                }
                s.push(i);
            }

            REP_1(i, m) checkMax(z, h[i]*(r[i]-l[i]));
        }
        OT(z);
    }
}

做法二：悬线法

//}/* .................................................................................................................................. */

const int N = int(2e3) + 9;

int A[N][N], h[N][N], l[N][N], r[N][N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
        //freopen("out.txt", "w", stdout);
#endif

    fill(A[0], A[0]+N, 1);
    fill(r[0], r[0]+N, INF);

    while (~scanf("%d %d", &n, &m)){


        REP_2_1(i, j, n, m) RD(A[i][j]);

        int z = 0; RST(h, l, r); REP_1(i, n){

            FOR_1(j, 1, m) l[i][j] = A[i][j] ? l[i][j-1] + 1 : 0;
            DWN_1(j, m, 1) r[i][j] = A[i][j] ? r[i][j+1] + 1 : 0;

            REP_1(j, m) if (A[i][j] && A[i-1][j]){
                h[i][j] = h[i-1][j] + 1;
                checkMin(l[i][j], l[i-1][j]);
                checkMin(r[i][j], r[i-1][j]);
            }
            REP_1(j, m) checkMax(z, (h[i][j]+1)*(r[i][j]+l[i][j]-1));
        }

        OT(z);
    }
}

Posted by xiaodao
Category: POJ