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月
動態(tài)規(guī)劃，利用子問題，向上，向下。。。
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, 0, sizeof(tri) );
60 memset( f, 0, sizeof(f) );
61 memset( g, 0, sizeof(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