poj 3494 dp+単調スタック

Larget Submatix of All 1’s
Time Limit: 5000 MS
 
メモリLimit: 131313722 K
Total Submissions: 5088
 
Acceepted: 1897
Case Time Limit: 2000 MS
Description
Given a m-by-n (0,1)-matrix、of all its submatirices of all 1’s which is the largest?By larget st we mean that the submatix has the most element.
Input
The input contains multiple test cases.Each test case begins with m and n (1≦ m, n ≦2000)オンライン.The n come the elemens of a(0,1)-marix in row-major order on m ラインeach with nnumbers.The input ends onece EOF is met.
Output
For each test case,output one line containing the number of elemens of the larget st submatirix of all 1’s.If the given marix is of all 0’s,output 0.
Sample Input

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

Sample Output

0
4

ソurce
POJ Founder Monthly Conttest–2008.01.31,xfxyjwf
最大サブマトリックスを求めます.各ビットは1です.
各行を列挙し、dp[n]前のn行の最大サブ行列は、最大サブ行列が最後の行を使用していない場合dp[n]=dp[n-1]です.n行目を使用すると、行列は連続していなければならないので、poj 2559のn個の幅は同じ1に変換できます.高さが違って最大面積の問題が求められます.単調なスタックですれば、O(n)の複雑さだけを利用できます.全体の複雑さはO(n^2)です.

#include 
#include 
#include 
#include 

using namespace std;

#define maxn 2001

int a[maxn][maxn];
int n, m;
int l[maxn], r[maxn];

int main()
{
    while(~scanf("%d %d", &m, &n)){
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        for(int j = 1; j <= n; j++)
            for(int i = 2; i <= m; i++)
            if(a[i-1][j] && a[i][j])
                a[i][j] += a[i-1][j];   //       i             1


        stack s;
        int ans = 0;
        for(int i = 1; i <= m; i++){
            while(!s.empty()) s.pop();
            for(int j = 1; j <= n; j++){    //  j      
                while(!s.empty() && a[i][s.top()] >= a[i][j]) s.pop();
                l[j] = s.empty() ? 1 : s.top()+1;
                s.push(j);
            }
            while(!s.empty()) s.pop();
            for(int j = n; j >= 1; j--){    //  j      
                while(!s.empty() && a[i][s.top()] >= a[i][j]) s.pop();
                r[j] = s.empty() ? n : s.top()-1;
                s.push(j);
            }

            for(int j = 1; j <= n; j++)
                ans = max(ans, (r[j]-l[j]+1)*a[i][j]);
        }

        printf("%d
", ans);


    }
    return 0;
}