算法题：uva 1330 - City Game

算法题：uva 1330 - City Game2014-03-17 csdn博客 shuangde800题目链接:

http://uva.onlinejudge.org/index.php？ option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076

以前做过一道一维的，这题只是变成了二维的，其他方法都一样。HDU 1506 Largest Rectangle in a Histogram 题解

代码1：

#include<cstdio>#include<cstring>#include<stack>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
", ans*3）;}int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--）{ solve（）;}return 0;}

代码2（栈扫描）：

#include<cstdio>#include<cstring>#include<stack>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<int>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
", ans*3）;}int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--）{ solve（）;}return 0;}