【数据结构】CODE[VS] 2491 && bzoj 3039玉蟾宫 (单调栈)

前端之家收集整理的这篇文章主要介绍了【数据结构】CODE[VS] 2491 && bzoj 3039玉蟾宫 (单调栈)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

点击观看<虹猫蓝兔七侠传>
点击观看<虹猫蓝兔七侠传(bzoj高端权限专版)>


题意是让你求最大子矩阵和
就是最大子段和的二维扩展
做的时候,还是需要一些技巧的


这道题直接暴力搜肯定会TLE(大师难度 ,出题人不可能出简单的暴搜)
我们可以将原图的R,F矩阵转化为01矩阵,然后按照行来遍历,每次记录当前行当前搜到的最大的向上为1的那一列的序号……额,给个图好了

然后,遇到1记录为 up[i][j] = up[i][j-1]类似于前缀和,遇到0重置为0

每行遍历的时候遇到比之前记录的最大值小的,就直接计算面积(长为最大值,宽为当前序号减去该列序号),每次与当前答案取max,遇到比当前最大的还大的,也采取类似操作即可,显然这些操作具有单调性,因此用到单调栈维护会简单很多
(STL大法好)

神犇们都说是大水题。。。。。。。。。。


代码如下:

  1. //gtnd zcw
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <stack>
  8.  
  9. const int maxn = 2000;
  10.  
  11. using namespace std;
  12.  
  13. int n,m;
  14. int map[maxn][maxn];
  15. int h[maxn][maxn];
  16. char c[1];
  17.  
  18. stack<int >s;
  19.  
  20. inline void rd(int &x)
  21. {
  22. scanf("%d",&x);
  23. }
  24.  
  25. inline void add()
  26. {
  27. for(int i = 1;i <= n;i++)
  28. for(int j = 1;j <= m;j++)
  29. {
  30. if(map[i][j] == 1) h[i][j] = h[i-1][j] + 1;
  31. else h[i][j] = 0;
  32. }
  33. }
  34.  
  35. inline void work()
  36. {
  37. for(int i = 1;i <= n;i++)
  38. for(int j = 1;j <= m;j++)
  39. {
  40. scanf("%s",c);
  41. if(c[0] == 'R') map[i][j] = 0;
  42. else map[i][j] = 1;
  43. }
  44. add();
  45. int ans = 0;
  46. //单调栈维护的是当前第i行上向上1数目最大的那一列的序号
  47. for(int i = 1;i <= n;i++)
  48. {
  49. for(int j = 1; j <= m;j++)
  50. {
  51. ans = max(ans,h[i][j]);
  52. int v = j;
  53. while(!s.empty() && h[i][j] < h[i][s.top()])
  54. {
  55. v = s.top();
  56. s.pop();
  57. ans = max(ans,(j-v) * h[i][v]);
  58. h[i][v] = h[i][j];
  59. }
  60. s.push(v);
  61. }
  62. while(!s.empty())
  63. {
  64. int u = s.top();
  65. s.pop();
  66. ans = max(ans,(m-u+1) * h[i][u]);
  67. }
  68. }
  69. printf("%d\n",ans*3);
  70. return ;
  71. }
  72.  
  73. int main()
  74. {
  75. rd(n);rd(m);
  76. work();
  77. return 0;
  78. }

THE END

By Peacefuldoge

http://blog.csdn.net/loi_peacefuldog/

猜你在找的数据结构相关文章