BZOJ-1057: [ZJOI2007]棋盘制作（悬线法解极大

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

悬线法求极大子矩阵，最初先把到左上角的点的曼哈顿距离为奇数的数去一次异或，然后跑两次极大子矩阵就可以了。

（悬线法其实挺容易的额。。。之前作为一个傻叉一直没去学，直到现在快省选了才脑残了过来补算法额。。。）

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define maxn 2010
#define clear( x ) memset( x , 0 , sizeof( x ) )
#define inf 0x7fffffff 
#define down( i , x ) for ( int i = x ; i ; -- i )
 
int ans0 = 0 , ans1 = 0 , n , m , a[ maxn ][ maxn ] ;
 
int h[ maxn ][ maxn ] , l[ maxn ][ maxn ] , r[ maxn ][ maxn ] ;
 
void Solve(  ) {
    clear( h ) , clear( l ) , clear( r ) ;
    rep( i , n ) rep( j , m ) if ( ! a[ i ][ j ] ) {
        h[ i ][ j ] = h[ i - 1 ][ j ] + 1 ;
    }
    rep( i , m ) l[ 0 ][ i ] = - inf , r[ 0 ][ i ] = inf ;
    rep( i , n ) {
        int temp = 1 ;
        rep( j , m ) if ( ! a[ i ][ j ] ) {
            l[ i ][ j ] = temp ;
            if ( ! a[ i - 1 ][ j ] && i - 1 ) l[ i ][ j ] = max( l[ i ][ j ] , l[ i - 1 ][ j ] ) ;
        } else temp = j + 1 ;
    }
    rep( i , n ) {
        int temp = m ; 
        down( j , m ) if ( ! a[ i ][ j ] ) {
            r[ i ][ j ] = temp ;
            if ( ! a[ i - 1 ][ j ] && i - 1 ) r[ i ][ j ] = min( r[ i ][ j ] , r[ i - 1 ][ j ] ) ;
        } else temp = j - 1 ;
    }
    rep( i , n ) rep( j , m ) if ( ! a[ i ][ j ] ) {
        ans0 = max( ans0 , h[ i ][ j ] * ( r[ i ][ j ] - l[ i ][ j ] + 1 ) ) ;
        int rec = min( h[ i ][ j ] , r[ i ][ j ] - l[ i ][ j ] + 1 ) ;
        ans1 = max( ans1 , rec * rec ) ;
    }
}
 
int main(  ) {
    scanf( "%d%d" , &n , &m ) ;
    rep( i , n ) rep( j , m ) scanf( "%d" , &a[ i ][ j ] ) ;
    rep( i , n ) rep( j , m ) if ( ( i + j ) & 1 ) a[ i ][ j ] ^= 1 ;
    Solve(  ) ;
    rep( i , n ) rep( j , m ) a[ i ][ j ] ^= 1 ;
    Solve(  ) ;
    printf( "%d\n%d\n" , ans1 , ans0 ) ;
    return 0 ; 
}