本文共 2509 字，大约阅读时间需要 8 分钟。
题目链接:
以前做过一道一维的，这题只是变成了二维的，其他方法都一样。
代码1：
#include#include #include using std::stack;const int MAXN = 1010;char str[MAXN*3];int sum[MAXN][MAXN];int left[MAXN], right[MAXN];int n, m;inline void input(){ scanf("%d%d%*c", &n, &m); for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ char ch = getchar(); while(ch!='F' && ch!='R') ch=getchar(); sum[i][j] = ch=='R'?0:1; if(sum[i][j]) sum[i][j] += sum[i-1][j]; } } }inline void solve(){ input(); int ans = 0; for(int i=1; i<=n; ++i){ sum[i][0] = sum[i][m+1] = -1; for(int j=1; j<=m; ++j) left[j]=right[j]=j; for(int j=1; j<=m; ++j){ while(sum[i][j] <= sum[i][left[j]-1]) left[j] = left[left[j]-1]; } for(int j=m; j>=1; --j){ while(sum[i][j] <= sum[i][right[j]+1]) right[j] = right[right[j]+1]; int tmp = (right[j]-left[j]+1)*sum[i][j]; if(tmp > ans) ans=tmp; } } printf("%d\n", ans*3);}int main(){ int nCase; scanf("%d", &nCase); while(nCase--){ solve(); } return 0;}
代码2（栈扫描）：
#include#include #include using std::stack;const int MAXN = 1010;char str[MAXN*3];int sum[MAXN][MAXN];int n, m;inline void input(){ scanf("%d%d%*c", &n, &m); memset(sum, 0, sizeof(sum)); for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ char ch = getchar(); while(ch!='F' && ch!='R') ch=getchar(); sum[i][j] = ch=='R'?0:1; if(sum[i][j]) sum[i][j] += sum[i-1][j]; } } }inline void solve(){ input(); int ans = 0; for(int i=1; i<=n; ++i){ sum[i][0] = sum[i][m+1] = -1; stack q; for(int j=1; j<=m+1; ++j){ if(q.empty() || sum[i][j]>sum[i][q.top()]){ q.push(j); } else if(sum[i][j] < sum[i][q.top()]){ int pos; while(!q.empty() && sum[i][q.top()]>sum[i][j]){ int tmp = (j-q.top())*sum[i][q.top()]; if(tmp > ans) ans = tmp; pos = q.top(); q.pop(); } q.push(pos); sum[i][pos] = sum[i][j]; } } } printf("%d\n", ans*3);}int main(){ int nCase; scanf("%d", &nCase); while(nCase--){ solve(); } return 0;}
转载地址：http://vszni.baihongyu.com/