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 阅读(1215) 评论(0)  编辑 收藏 引用 所属分类: ACM


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