gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 3494--Largest Submatrix of All 1’s(路径压缩)

 

 

  1#include <cstdio>
  2#include <cstring>
  3
  4const int MAXN = 4008 ;
  5const int SIZE = 2003 ;
  6
  7int left[SIZE], right[SIZE] ;
  8int height[SIZE] ;
  9
 10int GetMaxArea(const int& len)
 11{
 12    int i , j , temp , maxArea ;
 13    maxArea = 0 ;
 14
 15    height[0] = height[len + 1] = -1 ;
 16
 17
 18    for ( i = 1 ; i <= len ; ++i )
 19    {
 20        for ( j = i - 1 ; ; j = left[j] )
 21        {
 22            if ( height[j] < height[i] )
 23            {
 24                left[i] = j ;
 25                break ;
 26            }
 27        }
 28    }
 29
 30    for ( i = len ; i > 0 ; --i )
 31    {
 32        for ( j = i + 1 ; ; j = right[j] )
 33        {
 34            if ( height[j] < height[i] )
 35            {
 36                right[i] = j ;
 37                break ;
 38            }
 39        }
 40    }
 41
 42    for ( i = 1 ; i <= len ; ++i )
 43    {
 44        if ( height[i] !=  height[i - 1] )
 45        {
 46            temp = height[i] * (right[i] - left[i] - 1) ;
 47
 48            if ( temp > maxArea )
 49                maxArea = temp ;
 50        }
 51    }
 52
 53    return maxArea ;
 54
 55}
 56
 57int main()
 58{
 59//    freopen("1.txt", "r", stdin) ;
 60
 61    int row , col , i , j ;
 62    int ans , temp , num ;
 63    char strData[MAXN] ;
 64
 65    while ( scanf("%d %d", &row, &col) != EOF )
 66    {
 67        getchar() ;
 68        gets(strData) ;
 69        for ( j = 1 ; j <= col ; ++j )
 70        {
 71            height[j] = strData[(j - 1) * 2] - '0' ;
 72        }
 73
 74        ans = GetMaxArea(col) ;
 75
 76        for ( i = 1 ; i < row ; ++i )
 77        {
 78            gets(strData) ;
 79
 80            for ( j = 1 ; j <= col ; ++j )
 81            {
 82                num = strData[(j - 1) * 2] - '0' ;
 83                if ( 0 == num ) {
 84                    height[j] = 0 ;
 85                }
 86                else  if ( 1 == num ) {
 87                    height[j]++ ;
 88                }
 89            }
 90
 91            temp = GetMaxArea(col) ;
 92
 93            if ( temp > ans ) 
 94                ans = temp ;
 95        }
 96
 97        printf("%d\n", ans) ;
 98    }
 99    return 0 ;
100}
posted on 2009-03-06 11:10 巫 阅读(237) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理