某岛

… : "…アッカリ～ン . .. . " .. .

June 29, 2015

POJ 3494. Largest Submatrix of All 1’s

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

某岛

POJ 3494. Largest Submatrix of All 1’s

Archives

Blogroll

Links

Myself

Project