BZOJ-3039: 玉蟾宫(悬线法 极大子矩阵)
2018-11-29 本文已影响0人
AmadeusChan
代码:http://www.lydsy.com/JudgeOnline/problem.php?id=3039
刚刚学了悬线法,恰好看到一道极大子矩阵的水题,然后就水掉了(不懂悬线法的去看王知昆的集训队论文就好了)。
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define maxn 1010
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define down( i , x ) for ( int i = x ; i ; -- i )
#define inf 0x7fffffff
#define check( ch ) ( ch == 'F' || ch == 'R' )
#define clear( x ) memset( x , 0 , sizeof( x ) )
int h[ maxn ][ maxn ] , l[ maxn ][ maxn ] , r[ maxn ][ maxn ] ;
char s[ maxn ][ maxn ] ;
int n , m , ans = 0 ;
char getchr( ) {
int ch ; for ( ch = getchar( ) ; ! check( ch ) ; ch = getchar( ) ) ;
return char( ch ) ;
}
int main( ) {
scanf( "%d%d" , &n , &m ) ;
rep( i , n ) rep( j , m ) s[ i ][ j ] = getchr( ) ;
clear( h ) , clear( l ) , clear( r ) ;
rep( i , n ) rep( j , m ) if ( s[ i ][ j ] == 'F' ) h[ i ][ j ] = h[ i - 1 ][ j ] + 1 ;
rep( i , n ) {
int temp = 1 ;
rep( j , m ) if ( s[ i ][ j ] == 'F' ) {
l[ i ][ j ] = temp ;
if ( s[ i - 1 ][ j ] == 'F' ) l[ i ][ j ] = max( l[ i - 1 ][ j ] , l[ i ][ j ] ) ;
} else temp = j + 1 ;
}
rep( i , n ) {
int temp = m ;
down( j , m ) if ( s[ i ][ j ] == 'F' ) {
r[ i ][ j ] = temp ;
if ( s[ i - 1 ][ j ] == 'F' ) r[ i ][ j ] = min( r[ i ][ j ] , r[ i - 1 ][ j ] ) ;
} else temp = j - 1 ;
}
rep( i , n ) rep( j , m ) if ( s[ i ][ j ] == 'F' ) {
ans = max( ans , h[ i ][ j ] * ( r[ i ][ j ] - l[ i ][ j ] + 1 ) ) ;
}
printf( "%d\n" , ans * 3 ) ;
return 0 ;
}