• <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>

            coreBugZJ

            此 blog 已棄。

            Suneast’s blocks , FZU 2011年3月月賽之 B, FZU 2011

            Problem 2011 Suneast’s blocks

            Time Limit: 1000 mSec    Memory Limit : 32768 KB

            Problem Description

            Suneast loves playing with blocks so much. He has many small triangle blocks:

            He always likes using these small block to make a bigger one:

            The size of the small triangle is 1 and different block has different color, each color is expressed using an UPPER case alpha, so we can represent the big triangle above as the figure shows on the right.('~' means BLANK here)

            Now, Suneast want to know, what is the size of the largest sub-strangle with the same color within the bigger one.

            Input

            The first line of the input data is an integer number T, represent the number of test cases.

            The first line of each test case has an integer N (1<=n<=100), means the height of the big triangle. Then following N lines, each line has exactly 2*i-1 UPPER case letters represent the small triangle.

            Output

            For each test case, output a single line “Case %d: The largest block is %d.”, the first %d means the current case index, and the second %d is the size of the largest block.

            Sample Input

            3
            3
            A
            BCD
            EFDDD
            4
            A
            CCA
            CAAAC
            CACACAC
            4
            T
            ORZ
            DAXIA
            YAYAMAO

            Sample Output

            Case 1: The largest block is 4.
            Case 2: The largest block is 4.
            Case 3: The largest block is 1.

            Source

            FOJ有獎月賽-2011年03月


            動態規劃,利用子問題,向上,向下。。。


             1 #include <stdio.h>
             2 #include <string.h>
             3 
             4 #define  L  209
             5 
             6 int n, f[ L ][ L ], g[ L ][ L ];
             7 char  tri[ L ][ L ];
             8 
             9 int checkF( int i, int j ) {
            10         int a = ( (tri[i+1][j-1]==tri[i][j]) ? f[i+1][j-1] : 0 );
            11         int b = ( (tri[i+1][j+1]==tri[i][j]) ? f[i+1][j+1] : 0 );
            12         int c = ( a < b ? a : b );
            13         return f[ i ][ j ] = ( (tri[i+1][j]==tri[i][j]) ? (c+1) : 1 );
            14 }
            15 
            16 int checkG( int i, int j ) {
            17         int a = ( (tri[i-1][j-1]==tri[i][j]) ? g[i-1][j-1] : 0 );
            18         int b = ( (tri[i-1][j+1]==tri[i][j]) ? g[i-1][j+1] : 0 );
            19         int c = ( a < b ? a : b );
            20         return g[ i ][ j ] = ( (tri[i-1][j]==tri[i][j]) ? (c+1) : 1 );
            21 }
            22 
            23 int solve() {
            24         int i, j, h = 0, tmp, ans = 0;
            25         for ( i = n; i >= 1--i ) {
            26                 for ( j = n-i+1; j <= n+i-1; j+=2 ) {
            27                         tmp = checkF( i, j );
            28                         if ( tmp > h ) {
            29                                 h = tmp;
            30                         }
            31                 }
            32         }
            33         for ( i = 2; i <= n; ++i ) {
            34                 for ( j = n-i+2; j <= n+i-1; j+=2 ) {
            35                         tmp = checkG( i, j );
            36                         if ( tmp > h ) {
            37                                 h = tmp;
            38                         }
            39                 }
            40         }
            41         for ( i = 1; i <= h; ++i ) {
            42                 ans += i + i - 1;
            43         }
            44         return ans;
            45 }
            46 
            47 char next() {
            48         char ch;
            49         do {
            50                 ch = getchar();
            51         } while ( (ch<'A'|| ('Z'<ch) );
            52         return ch;
            53 }
            54 
            55 int main() {
            56         int td, cd = 0, i, j;
            57         scanf( "%d"&td );
            58         while ( td-- > 0 ) {
            59                 memset( tri, 0sizeof(tri) );
            60                 memset( f, 0sizeof(f) );
            61                 memset( g, 0sizeof(g) );
            62                 scanf( "%d"&n );
            63                 for ( i = 1; i <= n; ++i ) {
            64                         for ( j = n-i+1; j <= n+i-1++j ) {
            65                                 tri[ i ][ j ] = next();
            66                         }
            67                 }
            68                 printf( "Case %d: The largest block is %d.\n"++cd, solve() );
            69         }
            70         return 0;
            71 }
            72 


            posted on 2011-03-20 19:01 coreBugZJ 閱讀(1268) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久精品无码一区二区app| 精品久久久中文字幕人妻| 久久这里只精品国产99热| 久久精品国产99国产精品| 久久人妻AV中文字幕| 久久777国产线看观看精品| 久久久精品国产亚洲成人满18免费网站| 三级三级久久三级久久| 久久国产精品-国产精品| 久久精品国产乱子伦| 精品久久久久久无码中文野结衣| 久久中文字幕人妻熟av女| 国产成人久久精品二区三区| 天天躁日日躁狠狠久久 | 无夜精品久久久久久| AAA级久久久精品无码片| 久久久高清免费视频| 久久99精品国产麻豆蜜芽| 久久美女人爽女人爽| 91精品国产91久久综合| 人妻无码中文久久久久专区| 久久久午夜精品福利内容| 精品久久久久久无码国产| 91久久精品电影| 久久免费精品视频| 久久亚洲私人国产精品vA| 久久国产劲爆AV内射—百度| 人人狠狠综合久久亚洲| 久久夜色精品国产www| 国产精品免费久久久久影院| 中文字幕久久欲求不满| 久久亚洲高清观看| 美女写真久久影院| 国产精品伦理久久久久久| 91亚洲国产成人久久精品| 国产精品欧美久久久久天天影视 | 久久国产成人精品国产成人亚洲| 伊人久久综在合线亚洲2019 | 日韩一区二区三区视频久久| 93精91精品国产综合久久香蕉| 一级做a爰片久久毛片16|