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; }