BZOJ-3208: 花神的秒题计划Ⅰ（模拟+DFS）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3208

刚开始看到操作以为又是一道神题，动态树神马的，结果一看S+Q+B<=100就傻了：这不就一裸模拟维护么。。。取最值的时候就直接一遍记忆化DFS就好了。。。

代码：

1e30e924b899a9013d78c4531f950a7b0208f502.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 710
 
int h[ MAXN ][ MAXN ] , n , m , dp[ MAXN ][ MAXN ] ;
bool flag[ MAXN ][ MAXN ] ;
 
int dfs( int x , int y ) {
    if ( x <= 0 || y <= 0 || x > n || y > n ) return 0 ;
    if ( ! flag[ x ][ y ] ) return 0 ; 
    if ( dp[ x ][ y ] ) return dp[ x ][ y ] ;
    dp[ x ][ y ] = 1 ;
    if ( h[ x - 1 ][ y ] < h[ x ][ y ] ) dp[ x ][ y ] = max( dp[ x ][ y ] , dfs( x - 1 , y ) + 1 ) ;
    if ( h[ x + 1 ][ y ] < h[ x ][ y ] ) dp[ x ][ y ] = max( dp[ x ][ y ] , dfs( x + 1 , y ) + 1 ) ;
    if ( h[ x ][ y - 1 ] < h[ x ][ y ] ) dp[ x ][ y ] = max( dp[ x ][ y ] , dfs( x , y - 1 ) + 1 ) ;
    if ( h[ x ][ y + 1 ] < h[ x ][ y ] ) dp[ x ][ y ] = max( dp[ x ][ y ] , dfs( x , y + 1 ) + 1 ) ;
    return dp[ x ][ y ] ;
}
 
int main(  ) {
    scanf( "%d" , &n ) ;
    for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < n ; ) scanf( "%d" , &h[ i ][ j ] ) ;
    memset( flag , true , sizeof( flag ) ) ;
    scanf( "%d" , &m ) ;
    while ( m -- ) {
        int ch ; for ( ch = getchar(  ) ; ! ( ch >= 'A' && ch <= 'Z' ) ; ch = getchar(  ) ) ;
        if ( ch == 'C' ) {
            int a , b , c ; scanf( "%d%d%d" , &a , &b , &c ) ;
            h[ a ][ b ] = c ;
        } else if ( ch == 'S' ) {
            int a , b , c , d ; scanf( "%d%d%d%d" , &a , &b , &c , &d ) ;
            for ( int i = a ; i <= c ; i ++ ) for ( int j = b ; j <= d ; j ++ ) flag[ i ][ j ] = false ;
        } else if ( ch == 'B' ) {
            int a , b , c , d ; scanf( "%d%d%d%d" , &a , &b , &c , &d ) ;
            for ( int i = a ; i <= c ; i ++ ) for ( int j = b ; j <= d ; j ++ ) flag[ i ][ j ] = true ;
        } else {
            for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < n ; ) dp[ i ][ j ] = 0 ;
            int ans = 0 ;
            for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < n ; ) if ( flag[ i ][ j ] ) {
                if ( ! dp[ i ][ j ] ) dfs( i , j ) ;
                ans = max( ans , dp[ i ][ j ] ) ;
            }
            printf( "%d\n" , ans ) ;
        }
    }
    return 0 ; 
}