gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks

用PKU 2559的思路
跟2559一样还有DP解法:路径压缩

  1
  2#include <cstdio>
  3#include <cstring>
  4
  5const int SIZE = 1002 ;
  6
  7struct STACK
  8{
  9    int ht ;
 10    int pos ;
 11}
 ;
 12
 13STACK stack[SIZE] ;
 14int top ;
 15
 16int row , col , height[SIZE] ;
 17
 18int GetMaxArea()
 19{
 20    int ans , temp ;
 21    int i ;
 22    
 23    top  = 0 ;
 24    
 25    stack[top].ht = height[0] ;
 26    stack[top].pos = 0 ;
 27    ans = height[0] ;
 28    height[col] = 0 ;
 29
 30    for ( i = 1 ; i <= col ; ++i )
 31    {
 32        if ( height[i] <= stack[top].ht )
 33        {
 34            while ( top >= 0 && height[i] <= stack[top].ht )
 35            {
 36                temp = stack[top].ht * (i - stack[top].pos) ;
 37
 38                if ( temp > ans )
 39                    ans = temp ;
 40
 41                top-- ;
 42            }

 43            top++ ;
 44            stack[top].ht = height[i] ;
 45        }

 46        else {
 47            stack[++top].ht = height[i] ;
 48            stack[top].pos = i ;
 49        }

 50    }

 51        
 52    return ans ;
 53}

 54
 55
 56
 57int main()
 58{
 59    //freopen("1.txt", "r", stdin) ;
 60
 61    int test ;
 62    int maxProfit , temp , i , j ;
 63    char ch ;
 64
 65    scanf("%d"&test) ;
 66
 67    while ( test-- )
 68    {
 69
 70        scanf("%d %d"&row, &col) ;
 71        getchar() ;
 72
 73        maxProfit = 0 ;
 74
 75        j = 0 ;
 76
 77        while ( true ) {
 78            ch = getchar() ;
 79
 80            if ( ch == 'R' ) {
 81                height[j++= 0 ;
 82            }

 83            else if ( ch == 'F' ) {
 84                height[j++= 1 ;
 85            }

 86
 87            if ( j == col )
 88                break ;
 89        }

 90
 91
 92        for ( i = 1 ; i < row ; ++i )
 93        {
 94            j = 0 ;
 95
 96            while ( true ) {
 97                ch = getchar() ;
 98
 99                if ( ch == 'R' ) {
100                    height[j++= 0 ;
101                }

102                else if ( ch == 'F' ) {
103                    height[j++]++ ;
104                }

105
106                if ( j == col )
107                    break ;
108            }

109        
110            temp = GetMaxArea() ;
111
112            if ( temp > maxProfit )
113                maxProfit = temp ;
114        }

115
116        printf("%d\n", (maxProfit * 3)) ;
117
118
119    }

120    return 0 ;
121}

122
posted on 2009-03-05 23:56 阅读(280) 评论(0)  编辑 收藏 引用 所属分类: DP

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