P1950 长方形
题目描述
小明今天突发奇想，想从一张用过的纸中剪出一个长方形。
为了简化问题，小明做出如下规定：
（1）这张纸的长宽分别为 $n,m$。小明将这张纸看成是由$n\times m$个格子组成，在剪的时候，只能沿着格子的边缘剪。
（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。
（3）剪出来的长方形的大小没有限制。
小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？
输入格式
第一行两个正整数 $n,m$，表示这张纸的长度和宽度。
接下来有 $n$ 行，每行 $m$ 个字符，每个字符为 * 或者 .。
字符 * 表示以前在这个格子上画过，字符 . 表示以前在这个格子上没画过。
输出格式
仅一个整数，表示方案数。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
7
| 6 4
....
.***
.*..
.***
...*
.***
|
输出 #1
说明/提示
【数据规模】
对 $10%$ 的数据，满足 $1\leq n\leq 10,1\leq m\leq 10$
对 $30%$ 的数据，满足 $1\leq n\leq 50,1\leq m\leq 50$
对 $100%$ 的数据，满足 $1\leq n\leq 1000,1\leq m\leq 1000$
单调栈
- 可用于找某个元素一侧第一个比它小的元素 或按递增顺序比它大的所有元素(可形象理解为它的某一侧所有能看见它的元素_P2866)
- 维护一个单调递增的栈
- 当该元素比栈顶元素小时 将栈顶出栈
- 易知某个元素出栈时就找到了它某一侧(取决于遍历方向)第一个比它小的元素
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <iostream>
#define MAXN 1010
char ch[MAXN][MAXN];
int n, m, top;
int h[MAXN], l[MAXN], r[MAXN], st[MAXN];
long long ans;
using namespace std;
int main() {
cin >> n >> m;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin >> ch[i][j];
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
h[j] = ch[i][j] == '.' ? h[j]+1 : 0;
}
top = 0;
for(int j=1; j<=m; j++) {
while(top > 0 && h[j]<h[st[top]]) {
r[st[top]] = j;
top--;
}
st[++top] = j;
}
while(top > 0) {
r[st[top]] = m+1;
top--;
}
for(int j=m; j>=1; j--) {
while(top > 0 && h[st[top]] >= h[j]) {
l[st[top]] = j;
top--;
}
st[++top] = j;
}
while(top > 0) {
l[st[top]] = 0;
top--;
}
for(int j=1; j<=m; j++) {
ans += (j-l[j]) * (r[j]-j) * h[j];
}
}
printf("%lld\n", ans);
return 0;
}
|
