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

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

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

 

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