hdu1506的加强版, 如果要做这题,还是先去做1505吧

这一题,其实是对每一行做1505的那种dp,然后取最大值就行了。

 1 #pragma warning(disable:4996)
 2 #pragma comment(linker, "/STACK:1024000000,1024000000")
 3 #include <stdio.h>
 4 #include <string.h>
 5 #include <time.h>
 6 #include <math.h>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <stack>
11 #include <vector>
12 #include <bitset>
13 #include <algorithm>
14 #include <iostream>
15 #include <string>
16 #include <functional>
17 #include <unordered_map>
18 typedef __int64 LL;
19 const int INF = 999999999;
20 
21 
22 const int N = 1000 + 10;
23 int a[N][N];
24 int sum[N][N];
25 int left[N], right[N];
26 int main()
27 {    
28     char str[11];
29     int t, n, m;
30     scanf("%d", &t);
31     while (t--)
32     {
33         scanf("%d%d", &n, &m);
34         for (int i = 1;i <= n;++i)
35         {
36             for (int j = 1;j <= m;++j)
37             {
38                 scanf("%s", str);
39                 if (str[0] == \'R\')
40                     a[i][j] = 1;
41                 else
42                     a[i][j] = 0;
43                 
44                 //得到每一行的高度
45                 if (a[i][j] == 0)
46                     sum[i][j] = sum[i - 1][j] + 1;
47                 else
48                     sum[i][j] = 0;
49             }
50         }
51         int ans = 0;
52         for (int i = 1;i <= n;++i)
53         {
54             left[1] = right[m] = 0;
55             int l, r;
56             for (int j = 2;j <= m;++j)
57             {
58                 left[j] = 0;
59                 l = j - 1;
60                 while (l>=1 && sum[i][j] <= sum[i][l])
61                 {
62                     left[j] += left[l] + 1;
63                     l = l - left[l] - 1;
64                 }
65             }
66             for (int j = m - 1;j >= 1;--j)
67             {
68                 right[j] = 0;
69                 r = j + 1;
70                 while (r <= n && sum[i][j] <= sum[i][r])
71                 {
72                     right[j] += right[r] + 1;
73                     r = r + right[r] + 1;
74                 }
75             }
76             for (int j = 1;j <= m;++j)
77                 ans = std::max(ans, (left[j] + right[j] + 1)*sum[i][j]);
78         }
79         printf("%d\n", ans*3);
80     }
81     return 0;
82 }

 

版权声明:本文为justPassBy原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/justPassBy/p/4783304.html