UVA12265-Selling Land(单调栈)
Accept: 137 Submit: 782
Time Limit: 3000 mSec
Problem Description
Input
On the first line a positive integer: the number of test cases, at most 100. After that per test case:
• One line with two integers n and m (1 ≤ n,m ≤ 1000): the dimensions of Per’s parcel.
• n lines, each with m characters. Each character is either ‘#’ or ‘.’. The j-th character on the i-th line is a ‘#’ if position (i,j) is a swamp, and ‘.’ if it is grass. The north-west corner of Per’s parcel has coordinates (1, 1), and the south-east corner has coordinates (n,m).
Output
Sample Input
6 5
..#.#
.#...
#..##
...#.
#....
#..#.
Sample Output
6 x 4
5 x 6
5 x 8
3 x 10
1 x 12
题解:很多类似的有障碍物的关于矩形的题都会用到单调栈,算是个小经验吧,以后再碰到这类题多往这边想想。预处理一个最高延伸高度的height数组是非常自然的,在处理每一列时,如果当前列高度大于栈顶元素的高度,只用分析当前列是否可能成为最优解,如果可能就压入栈中,否则继续遍历。如果当前列高度小于等于栈顶元素,那就需要弹栈了,直到栈顶元素高度小于当前列高度,这时判断是否时最优解时,用的不是当前列的列数,而是弹栈的最后一个元素的列数,这是因为要最大化h-c,相同的方法判断能否成为最优解,决定是否压入栈中即可。
#include <bits/stdc++.h> using namespace std; const int maxn = + ; int n, m;
int height[maxn], ans[maxn << ];
char gra[maxn][maxn]; struct Node {
int c, h;
Node() {}
Node(int _c, int _h) : c(_c), h(_h) {}
}; int main()
{
//freopen("input.txt", "r", stdin);
int iCase;
scanf("%d", &iCase);
while (iCase--) {
scanf("%d%d", &n, &m);
for (int i = ; i < n; i++) {
scanf("%s", gra[i]);
}
memset(height, , sizeof(height));
memset(ans, , sizeof(ans)); for (int i = ; i < n; i++) {
stack<Node> sta;
while (!sta.empty()) sta.pop();
for (int j = ; j < m; j++) {
if (gra[i][j] == '#') {
while (!sta.empty()) sta.pop();
height[j] = ;
}
else {
height[j]++;
Node tmp(j, height[j]);
while (!sta.empty() && sta.top().h >= tmp.h) {
tmp.c = sta.top().c;
sta.pop();
} if (sta.empty()) {
sta.push(tmp);
}
else {
Node top = sta.top();
if (top.h - top.c < tmp.h - tmp.c) sta.push(tmp);
}
Node top = sta.top();
ans[j - top.c + top.h + ]++;
}
}
} for (int i = ; i <= n + m; i++) {
if (ans[i]) printf("%d x %d\n", ans[i], i * );
}
}
return ;
}
最新文章
- 【所见即所得】textarea 精确限制字数、行数,中、英、全半角混检 。源码带注释
- Python入门神图
- linux 打包压缩工具
- oracle查询表的索引
- CentOS7.0安装JDK1.8.0_31
- SQL技术内幕-12 SQL优化方法论前言
- Linux C++服务器程序设计范式
- qsort排序算法
- oracle Recyclebin
- HDU 2553 N皇后问题(dfs)
- android4.4组件分析--service组件-bindService源代码分析
- ElasticSearch和Kibana 5.X集群的安装
- ios自带的返回按键,点击不刷新页面
- Ext使用中问题总结
- Hive之SerDe&;Beeline
- java支付宝接口开发
- c# BackgroundWorker初试
- eclipse启动tomcat访问http://localhost:8080 报404错误
- RTP 流媒体
- input type=";tel"; 输入框显示密文
热门文章
- Struts2_属性驱动
- 修改CentOS服务器时间为北京时间
- JavaScript是如何工作的:事件循环和异步编程的崛起 + 5种使用 async/await 更好地编码方式!
- Android实现图片的压缩、旋转工具类
- js 取数组中某个对象的集合
- 洛谷P5245 【模板】多项式快速幂(多项式ln 多项式exp)
- eNSP 常用操作
- Android--记录莫名其妙的引用、依赖冲突解决办法
- MySQL 博客文章目录(2017-02-18更新)
- [转载]Windows&#160;2003&#160;R2&#160;SP2&#160;VOL&#160;企业版(简体中文)