用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