hdu1505
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 版权协议,转载请附上原文出处链接和本声明。