• <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 閱讀(294) 評論(0)  編輯 收藏 引用 所屬分類: DP
            亚洲va久久久噜噜噜久久| 五月丁香综合激情六月久久| 久久99国产精品久久| 久久久老熟女一区二区三区| 久久精品国产亚洲av高清漫画| 久久国产精品-久久精品| 九九久久精品无码专区| 99精品伊人久久久大香线蕉| 久久久久久噜噜精品免费直播| 久久免费看黄a级毛片| 久久精品人人做人人爽电影| 久久婷婷五月综合成人D啪| 麻豆AV一区二区三区久久| 国产69精品久久久久99| 午夜不卡久久精品无码免费| 国产亚洲色婷婷久久99精品91| 日本WV一本一道久久香蕉| 99久久久久| 久久精品九九亚洲精品天堂| 色综合久久夜色精品国产| 国产福利电影一区二区三区,免费久久久久久久精 | 伊人久久综合无码成人网| 欧美牲交A欧牲交aⅴ久久| 久久久久国产精品嫩草影院| 国产91色综合久久免费| 婷婷久久久亚洲欧洲日产国码AV| 久久人妻少妇嫩草AV蜜桃| 国产精品久久网| avtt天堂网久久精品| 无码人妻久久一区二区三区| 久久只这里是精品66| 性做久久久久久免费观看| 国产精品内射久久久久欢欢| 亚洲精品高清国产一久久| 久久99精品久久久久久久不卡| 久久精品国产AV一区二区三区| 久久久久成人精品无码| 青青草原综合久久大伊人导航| 超级碰久久免费公开视频| 久久性生大片免费观看性| 色偷偷91久久综合噜噜噜噜|