【题目链接】

http://poj.org/problem?id=1964

【算法】

记f[i]表示第i行最多向上延伸的行数

然后,对于每一行,我们用单调栈计算出这一行向上延伸的最大矩形面积,取最大值,即可

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 1010 int T,n,m,i,j,ans;
int f[MAXN][MAXN];
char tmp[]; inline int getans(int *a)
{
int i,top = ,ans = ,tmp;
static int s[MAXN],w[MAXN];
s[] = a[m+] = -;
for (i = ; i <= m + ; i++)
{
if (a[i] >= s[top])
{
s[++top] = a[i];
w[top] = ;
} else
{
tmp = ;
while (a[i] < s[top])
{
tmp += w[top];
ans = max(ans,tmp*s[top]);
top--;
}
s[++top] = a[i];
w[top] = tmp + ;
}
}
return ans;
} int main()
{ scanf("%d",&T);
while (T--)
{
ans = ;
scanf("%d%d",&n,&m);
for (i = ; i <= n; i++)
{
for (j = ; j <= m; j++)
{
scanf("%s",&tmp);
f[i][j] = (tmp[] == 'F') ? (f[i-][j] + ) : ();
}
}
for (i = ; i <= n; i++) ans = max(ans,getans(f[i]));
printf("%d\n",ans*);
} return ; }

最新文章

  1. 从零开始编写自己的C#框架——框架学习补充说明
  2. IIS同时实现网站部分使用https协议访问另一部分http访问
  3. thinkphp3.1.3中widget用法
  4. 使用Application Insights 做分析
  5. C#三种判断字符是否为汉字的方法
  6. liunx下tomcat启动 Cannot find ./catalina.sh
  7. CLion注册码算法逆向分析实录
  8. 单片机 C 语言模块化编程
  9. SQL Server 2008启用sa账户
  10. UVa 11292 - Dragon of Loowater(排序贪心)
  11. vc6 pbo 文件为空的解决方法
  12. python——爬虫&amp;问题解决&amp;思考(1)
  13. Struts(十五):主题
  14. CF 441E Valera and Number
  15. nginx第三方库安装以及连接memcache
  16. 20165304《Java程序设计》第九周学习总结
  17. 使用Amalgamate将C/C++项目合并成一个.h/.c[pp]文件
  18. JsonPath:从多层嵌套Json中解析所需要的值
  19. 【转】如何打开注册表编辑器中存储用户信息的SAM文件?
  20. pandas 初识(四)

热门文章

  1. java 操作clob
  2. windows编译MaskRCNN
  3. C# 调用指定打印机 (并不是默认)
  4. centos7 安装zabbix3.4
  5. 《C++ Primer 第5版》第1章
  6. 移动端rem布局 js
  7. Django-cookie与session操作
  8. [TS-A1486][2013中国国家集训队第二次作业]树[树的重心,点分治]
  9. 本地数据文件加载到hive表
  10. N - Corporate Identity