点击观看<虹猫蓝兔七侠传>
点击观看<虹猫蓝兔七侠传(bzoj高端权限专版)>
题意是让你求最大子矩阵和
就是最大子段和的二维扩展
做的时候,还是需要一些技巧的
这道题直接暴力搜肯定会TLE(大师难度 ,出题人不可能出简单的暴搜)
我们可以将原图的R,F矩阵转化为01矩阵,然后按照行来遍历,每次记录当前行当前搜到的最大的向上为1的那一列的序号……额,给个图好了
然后,遇到1记录为 up[i][j] = up[i][j-1]类似于前缀和,遇到0重置为0
每行遍历的时候遇到比之前记录的最大值小的,就直接计算面积(长为最大值,宽为当前序号减去该列序号),每次与当前答案取max,遇到比当前最大的还大的,也采取类似操作即可,显然这些操作具有单调性,因此用到单调栈维护会简单很多
(STL大法好)
神犇们都说是大水题。。。。。。。。。。
代码如下:
- //gtnd zcw
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <cstdlib>
- #include <stack>
-
- const int maxn = 2000;
-
- using namespace std;
-
- int n,m;
- int map[maxn][maxn];
- int h[maxn][maxn];
- char c[1];
-
- stack<int >s;
-
- inline void rd(int &x)
- {
- scanf("%d",&x);
- }
-
- inline void add()
- {
- for(int i = 1;i <= n;i++)
- for(int j = 1;j <= m;j++)
- {
- if(map[i][j] == 1) h[i][j] = h[i-1][j] + 1;
- else h[i][j] = 0;
- }
- }
-
- inline void work()
- {
- for(int i = 1;i <= n;i++)
- for(int j = 1;j <= m;j++)
- {
- scanf("%s",c);
- if(c[0] == 'R') map[i][j] = 0;
- else map[i][j] = 1;
- }
- add();
- int ans = 0;
- //单调栈维护的是当前第i行上向上1数目最大的那一列的序号
- for(int i = 1;i <= n;i++)
- {
- for(int j = 1; j <= m;j++)
- {
- ans = max(ans,h[i][j]);
- int v = j;
- while(!s.empty() && h[i][j] < h[i][s.top()])
- {
- v = s.top();
- s.pop();
- ans = max(ans,(j-v) * h[i][v]);
- h[i][v] = h[i][j];
- }
- s.push(v);
- }
- while(!s.empty())
- {
- int u = s.top();
- s.pop();
- ans = max(ans,(m-u+1) * h[i][u]);
- }
- }
- printf("%d\n",ans*3);
- return ;
- }
-
- int main()
- {
- rd(n);rd(m);
- work();
- return 0;
- }
THE END
By Peacefuldoge