0w1

CFR 375 B. Maximum Submatrix 2 ( DP )

Problem - 375B - Codeforces
題意:
給一個 0/1 矩陣,求最大全 1 矩形面積。
解法:
先預處理
dp[ i ][ j ] : 在 row i, col j, 向右延伸連續 1 的最長長度。
接著對於每個固定左界,將每一行收集起來,由大到小排序。這時候就能 O( N ) 更新答案。

int N, M;
vs G;

void init(){
    cin >> N >> M;
    G = vs( N );
    for( int i = 0; i < N; ++i )
        cin >> G[ i ];
}

vvi dp; // length of maximum one consecutive to the right 

void preprocess(){
    dp = vvi( N, vi( M ) );
    for( int i = 0; i < N; ++i )
        for( int j = M - 1; j >= 0; --j ){
            if( G[ i ][ j ] == '0' )
                dp[ i ][ j ] = 0;
            else
                dp[ i ][ j ] = 1 + ( j + 1 == M ? 0 : dp[ i ][ j + 1 ] );
        }
}

void solve(){
    int ans = 0;
    for( int i = 0; i < M; ++i ){
        vi maxlen;
        for( int j = 0; j < N; ++j )
            maxlen.push_back( dp[ j ][ i ] );
        sort( maxlen.begin(), maxlen.end(), greater< int >() );
        for( int j = 0; j < N; ++j )
            upmax( ans, maxlen[ j ] * ( j + 1 ) );
    }
    cout << ans << endl;
}