hdu 2830 - Matrix Swapping II

题目：求一个01矩阵中的最大有全是1的矩形面积，列可以任意互换。

分析：dp。zoj2180类似题，计算前 K行的最大值时，先按高度排序即可。

            这里利用单调队列优化了查询算法，确定每个点右（左）边第一个比他小的点；

            即保存一个区间的最小高度维护即可；

            最大的面积为max（最小高度*区间长度），T（N）= N^2 log（N）。

说明：（2011-09-19 08:10）。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char maps[ 1005 ][ 1005 ];

int  D[ 1005 ];
int  S[ 1005 ];
int  L[ 1005 ];
int  R[ 1005 ];
int  SMQ[ 1005 ];

int cmp( const void* a, const void* b )
{
    return *((int *)a) - *((int *)b);
}

int main()
{
    int n,m;
    while ( ~scanf("%d%d",&n,&m) ) {
        for ( int i = 1 ; i <= n ; ++ i )
            scanf("%s",&maps[ i ][ 1 ]);
        
        memset( D, 0, sizeof( D ) );
        int Max = 0;
        for ( int i = 1 ; i <= n ; ++ i ) {
    
            for ( int j = 1 ; j <= m ; ++ j ) {
                if ( maps[ i ][ j ] == '1' ) ++ D[ j ];
                else D[ j ] = 0;
                S[ j ] = D[ j ];
            }
            
            qsort( &S[ 1 ], m, sizeof( int ), cmp );
            S[ 0 ] = S[ m+1 ] = -1;
            /*
            for ( int j = 1 ; j <= m ; ++ j )
                printf("%d",S[ j ]);
            printf("\n");
            */
            
            SMQ[ 0 ] =  0;
            int tail1 = 0;
            for ( int j = 1 ; j <= m+1 ; ++ j ) {
                while ( S[ SMQ[ tail1 ] ] > S[ j ] ) 
                    R[ SMQ[ tail1 -- ] ] = j;
                SMQ[ ++ tail1 ] = j;
            }
            SMQ[ 0 ] =  m+1;
            int tail2 = 0;
            for ( int j = m ; j >= 0 ; -- j ) {
                while ( S[ SMQ[ tail2 ] ] > S[ j ] ) 
                    L[ SMQ[ tail2 -- ] ] = j;
                SMQ[ ++ tail2 ] = j;
            }
            
            for ( int j = 1 ; j <= m ; ++ j )
                if ( Max < S[ j ]*(R[ j ]-L[ j ]-1) )
                    Max = S[ j ]*(R[ j ]-L[ j ]-1);
        }
        printf("%d\n",Max);
    }
    return 0;
}