给你 N×M 大的矩阵, 里面分别有字符'F'和'R', 要找到一个最大的只有'F'的矩阵, 不能包含有'R'.N,M<=1000.
一开始的思路是单调栈来求最大矩形面积, 因为没看清题目不能包含'R'字符, 所以算出每行的'F'字符个数然后单调栈就 WA 了..
然后想到要从左边开始, 算出连续的'F'字符个数, 然后又 WA 了.
因为还有右边, 所以右边开始的'F'字符也处理一下, 也是 WA.
接着想到这种情形:
R F F F R
R F F F R
这枚举 F 的开始结束的话都是不行的, 那么因为就两种字符. 然后我又上一步一样只是求出 R 连续的大小, 然后统计
lf 左边开始'F'的连续个数然后单调栈
rf 右边开始'F'的连续个数然后单调栈
lr 左边开始'R'的连续个数然后单调栈
rr 右边开始'R'的连续个数然后单调栈.
那么答案我就觉得是 max(lf,rf,n*m-max(lr,rr))
然后也 WA, 因为我想到一个反例:
R R R R R
R F F F R
R F F F R
R F F F R
R R R R R
仔细观察这个样例, 发现其实之前的做法很麻烦, 我们最后得出的矩形一定是有左边的 (废话), 但是这个左边不确定, 只要确定了直接用单调栈就出来了.
所以想到可以枚举 K 列, 每次从第 K 列开始算. 代码如下:
- #include <iostream>
- #include <fstream>
- #include <stdio.h>
- #include <string>
- #include <string.h>
- #include <algorithm>
- using namespace std;
- int n,m,arr[2333],stk[2333],w[2333];
- char ma[2333][2333],ss[233];
- long long ans;
- int main() {
- int k;
- scanf("%d",&k);
- while(k--) {
- long long lr,rr,lf,rf;
- lr=rr=lf=rf=0;
- memset(stk,0,sizeof stk);
- ans=0;
- memset(w,0,sizeof w);
- scanf("%d%d",&n,&m);
- for(int i=1; i<=n; ++i) {
- for(int j=1; j<=m; ++j)
- scanf("%s",ss),ma[i][j]=ss[0];
- }
- for(int k=1; k<=m; ++k) {
- for(int i=1; i<=n; ++i) {
- int tmp=0;
- int j=k;
- while(j<=m&&ma[i][j++]!='R')
- ++tmp;
- /*
- for(int j=1;j<=m;++j)
- if(ma[i][j]=='F')
- ++tmp;
- */
- arr[i]=tmp;
- }
- memset(stk,0,sizeof stk);
- memset(w,0,sizeof w);
- lf=0;
- arr[n+1]=0;
- int p=0;
- for(int i=1; i<=n+1; ++i) {
- if(arr[i]>stk[p])
- stk[++p]=arr[i],w[p]=1;
- else {
- int wid=0;
- while(stk[p]>arr[i]) {
- wid+=w[p];
- lf=max(lf,(long long)wid*stk[p]);
- --p;
- }
- stk[++p]=arr[i];
- w[p]=wid+1;
- }
- }
- ans=max(ans,lf);
- }
- printf("%lld\n",ans*3);
- }
- return 0;
- }
- POJ1964-City Game
来源: http://www.bubuko.com/infodetail-2579583.html