| 题目名称 | 2207. [USACO Jan16]哞哞城堡 |
|---|---|
| 输入输出 | fortmoo.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 13 |
| 题目来源 |
 Satoshi
于2016-04-04加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：8， 通过率：100% | ||||
 zhengtn03 |
100 | 0.077 s | 0.69 MiB | C++ |
 Zayin |
100 | 0.133 s | 1.41 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.161 s | 13.85 MiB | C++ |
 梦那边的美好ET |
100 | 0.181 s | 3.49 MiB | C++ |
 WangYenJen |
100 | 0.213 s | 0.52 MiB | C++ |
 Fancy |
100 | 0.238 s | 0.60 MiB | C++ |
|
科比_李牧然 |
100 | 0.257 s | 3.61 MiB | C++ |
 Satoshi |
100 | 0.374 s | 0.82 MiB | C++ |
| 本题关联比赛 | |||
| ZLXSCDay2 | |||
| 关于 哞哞城堡 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Satoshi :
人家是16年一月的题 瑆の時間~無盡輪迴·林蔭
2020-02-04 19:12
6楼
| ||||
|
回复 @Satoshi :
神兽一直都很6  asddddd
2016-04-09 15:28
5楼
| ||||
|
二维前缀和+单调队列，暴力是O((NM))^2的枚举矩形左上角和右下角，但是我们可以利用矩形的特殊性质，单调队列滑一滑就可以了，有时间写题解
| ||||
|
回复 @Satoshi :
他的意思是666- -  安呐一条小咸鱼。
2016-04-04 16:02
3楼
| ||||
|
回复 @叶子の宿敌 :
？？？？ Satoshi
2016-04-04 15:59
2楼
| ||||
|
我先不交了，坐等人民群众先A题
这题的思路比较巧妙 Satoshi
2016-04-04 15:15
1楼
| ||||
【题目描述】
Bessie正在和她的朋友 Elsie一起建造堡垒,正如任何好的堡垒一样，这需要一个稳定的框架，Bessie想要建一个一米宽的矩形框架,在上面她要建造堡垒。
Bessie早已选择了建造堡垒的区域:一片$N米长，M米宽(1<=M,N<=200)$的土地。
不幸的是，这个区域有很多不能在上面支撑框架的沼泽区域。请帮助Bessie找出堡垒的最大面积(用矩形框架作为支撑)，这样的支架不能建造在沼泽区域上。
【输入格式】
第一行两个整数N和M
接下来N行每行M个字符，形成一个网格描述这个区域。’.’表示普通的草,’X’表示沼泽地。
【输出格式】
只有一行一个正整数，为堡垒的最大面积。
【样例输入】
5 6
......
..X..X
X..X..
......
..X...
【样例输出】
16
【样例解释】
用字符'f'来表示矩形框架
.ffff.
.fX.fX
Xf.Xf.
.ffff.
..X...
面积为$4·4=16$
【提示】
对于53.8462%的数据,$N·M<=6000$
对于100%的数据，$1<=N,M<=200$
【来源】
USACO 2016 January contest Platinum