• <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
            青青草原综合久久大伊人导航| 色狠狠久久综合网| 人人狠狠综合久久88成人| 精品久久久久久99人妻| 久久婷婷五月综合色99啪ak| 久久丫忘忧草产品| 久久噜噜电影你懂的| 亚洲第一永久AV网站久久精品男人的天堂AV| 伊人久久大香线蕉综合网站| 亚洲精品无码成人片久久| 99久久99久久精品国产| 久久久久久综合网天天| 日本一区精品久久久久影院| 狠狠色丁香久久婷婷综合图片| 久久精品草草草| 久久人人爽人人爽人人AV| 久久人人爽人人爽人人片AV东京热| 久久久噜噜噜www成人网| 亚洲精品第一综合99久久| 嫩草伊人久久精品少妇AV| 日本精品久久久久影院日本| 韩国免费A级毛片久久| 国产精品一区二区久久精品涩爱| 色偷偷888欧美精品久久久| 欧美黑人激情性久久| 一本一本久久a久久综合精品蜜桃| 国产激情久久久久影院| 777米奇久久最新地址| 久久精品国产色蜜蜜麻豆| 日本加勒比久久精品| 久久天天躁狠狠躁夜夜不卡| 国内精品久久久久久久亚洲| 久久国产精品99精品国产987| 久久天天躁狠狠躁夜夜avapp| 久久亚洲sm情趣捆绑调教| 久久久黄色大片| 久久久噜噜噜久久中文字幕色伊伊| 婷婷久久综合九色综合绿巨人| 久久免费国产精品| 少妇熟女久久综合网色欲| 久久婷婷是五月综合色狠狠|