BZOJ-3039: 玉蟾宫（悬线法 极大子矩阵）

代码：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 ; 
}