• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(291) 評論(0)  編輯 收藏 引用 所屬分類: DP
            亚洲午夜精品久久久久久浪潮| 亚洲午夜无码AV毛片久久| 99久久国产综合精品网成人影院| 久久久久亚洲AV成人网人人网站| 久久人妻无码中文字幕| 久久精品亚洲中文字幕无码麻豆| 国产亚州精品女人久久久久久 | 国产成人综合久久精品红| 久久久精品人妻一区二区三区四| 亚洲国产成人久久综合一| 18岁日韩内射颜射午夜久久成人| 国产精品一区二区久久精品无码| 久久久久久精品久久久久| 精品久久久久中文字幕一区| 久久精品九九亚洲精品| 中文字幕无码av激情不卡久久| AA级片免费看视频久久| 久久亚洲精品成人av无码网站| 婷婷久久综合九色综合九七| 99久久精品免费观看国产| 国内精品久久久久影院优| 亚洲乱码精品久久久久..| 日韩va亚洲va欧美va久久| 国产精品欧美久久久久天天影视| 国产精品久久久久久久| 久久丫精品国产亚洲av| 新狼窝色AV性久久久久久| 噜噜噜色噜噜噜久久| 日本久久久久久久久久| 精品国产青草久久久久福利| 亚洲国产精品热久久| 青青草国产成人久久91网| 久久99精品久久久久久| 久久噜噜电影你懂的| 久久91精品国产91久久户| 久久中文娱乐网| 精品久久久久久无码中文字幕| 伊人久久大香线焦综合四虎| 国产高清美女一级a毛片久久w| 国产亚洲成人久久| 中文精品久久久久人妻|