[BZOJ4506] [Usaco2016 Jan]Fort Moo(DP?)
2024-08-30 05:18:57
总之可以先预处理出来每个位置最多往上延伸多少
枚举两行,看看夹在这两行中间的列最大能构成多大的矩形
可以看出,必须得在一个两行都没有X的区间才有可能构成最大的答案
那么可以把这些区间处理出来,在看看这些区间中的点最左边和最右边的能从下面那一行向上延伸到上面那一行的点,更新ans即可
#include <cstdio>
#define N 201
#define max(x, y) ((x) > (y) ? (x) : (y)) int n, m, ans, p;
int h[N][N], b[N];
char s[N][N]; int main()
{
int i, j, k;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
{
scanf("%s", s[i] + 1);
for(j = 1; j <= m; j++)
if(s[i][j] == '.')
h[i][j] = h[i - 1][j] + 1;
}
for(i = 1; i <= n; i++)
for(j = i + 1; j <= n; j++)
{
p = -1;
for(k = 1; k <= m; k++) b[k] = h[j][k];
for(k = 1; k <= m; k++)
if(s[i][k] == 'X')
b[k] = 0;
for(k = 1; k <= m; k++)
{
if(!b[k]) p = -1;
if(j - b[k] < i && p == -1) p = k;
if(j - b[k] < i && p != -1) ans = max(ans, (k - p + 1) * (j - i + 1));
}
}
printf("%d\n", ans);
return 0;
}
最新文章
- jekins 持续集成手记
- JS设置cookie、读取cookie、删除cookie
- hadoop fs 命令
- spring ehcache 页面、对象缓存
- 安装DotNetCore.1.0.0-VS2015Tools.Preview2失败解决方案
- ajax读取json数据
- 一个inline-block的样式。
- 【C#学习笔记】Dictionary容器使用
- [oracle]一个最简单的oracle存储过程";proc_helloworld";
- Android Gson使用笔记
- Failed to issue method call: Unit mysql.service failed to load: No such file or directory解决的方式
- Health Check in eShop -- 解析微软微服务架构Demo(五)
- Tp3.2提交表单与操作表单
- CSS继承、层叠和特殊性
- 在windows8.1下安装ubuntu16.04
- Apollo源码阅读笔记(一)
- 【入门推荐】SQL注入进行WebShell渗透测试的基础概览
- 3.23日PSP
- Oracle数据库备份还原工具之Expdp/IMPdp
- 【POJ1284】Primitive Roots