最近在学习单调桟,这个题目听有意思的,需要稍微动动心思,往poj 2559上想。但是时间总是1700MS左右,真不知道网上那些100ms是怎么出来的。
/** * poj_3494.cpp * */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; #define MN 2010 #define hpmax(a,b) ((a)>(b)?(a):(b)) #define hpmin(a,b) ((a)<(b)?(a):(b)) char matrix[MN][MN]; int bound[MN][MN], lmin[MN], rmin[MN]; int stack[MN]; int m, n, p; int main() { int i, j, ans, tmp, left, right; while ( scanf(" %d%d", &m, &n ) != EOF ) { for ( i = 1; i <= m; ++ i ) { for ( j = 1; j <= n; ++ j ) scanf(" %c", &matrix[i][j] ); } for ( i = 1; i <= m; ++ i ) { tmp = 0; for ( j = n; j >= 1; -- j ) { if ( '1' == matrix[i][j] ) ++ tmp; else tmp = 0; bound[i][j] = tmp; } } ans = 0; for ( j = 1; j <= n; ++ j ) { stack[0] = 0; bound[0][j] = -1; stack[1] = 1; lmin[1] = 0; p = 1; for ( i = 2; i <= m; ++ i ) { while ( p > 0 && bound[ stack[p] ][j] > bound[i][j] ) { rmin[ stack[p--] ] = i; } if ( bound[stack[p]][j] == bound[i][j]) lmin[i] = lmin[ stack[p] ]; else lmin[i] = stack[p]; stack[++p] = i; } while ( p > 0 ) { rmin[ stack[p--] ] = m+1; } for ( i = 1; i <= m; ++ i ) { tmp = bound[i][j] * ( rmin[i] - lmin[i] - 1 ); if ( tmp > ans ) ans = tmp; } } printf("%d\n", ans ); } return 0; }