洛谷P1950 长方形（单调栈）

一道单调栈的好题啊。。。。。。

思路是很奇妙的，对于每个点（i，j），我们可以算它对答案的贡献（即包含它的矩形数量），包含该点的矩形，点的高度为h[j]，点右边的高度一定大于等于h[j]，左边的高度一定大于h[j]。

高有h[j]种方案，底边有(j - lj) * (rj - j)种方案,相乘就是该点对答案的贡献。

具体步骤：

1.定义 h[j] 为当前行第 j 列可向上延伸多少（如果当前块被图画那么值为0）
2.使用单调栈算出 li 和 ri ，分别是 j中左边第一个（从 j 开始）不大于 h[j] 的数和右边第一个（从 j 开始）小于 h[j] 的数
3.(j-lj)*(rj-j)*h[j]的值就是每一个点所能组成的矩形的个数。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 char ch;

 4 long long l[1020],r[1020],h[1020],k[1020],n,m,top;

 5 int d[1020][1020];

 6 long long ans;

 7

 8 void ddzl(){//左

 9     top=0;

10     for(int i=m;i>=1;i--){

11         while(top!=0 && h[i]<=h[k[top]]) l[k[top--]]=i;

12         k[++top]=i;

13     }

14     while(top) l[k[top--]]=0;

15 }

16

17 void ddzr(){//右

18     top=0;

19     for(int i=1;i<=m;i++){

20         while(top!=0 && h[i]<h[k[top]]) r[k[top--]]=i;

21         k[++top]=i;

22     }

23     while(top) r[k[top--]]=m+1;

24 }

25

26 void work(){

27     ddzl();//求左边第一个小等于的下标

28     ddzr();//求右边第一个小于的下标

29     for(int i=1;i<=m;i++)

30         ans+=(i-l[i])*(r[i]-i)*h[i];//累加结果

31 }

32

33 int main(){

34     cin>>n>>m;

35     for(int i=1;i<=n;i++)

36     for(int j=1;j<=m;j++){

37         cin>>ch;

38         if(ch=='*') d[i][j]=1;//标记

39     }

40     for(int i=1;i<=n;i++){

41         for(int j=1;j<=m;j++){

42             h[j]++;

43             if(d[i][j]) h[j]=0;//求该列从最上面到j的最大延伸高度

44         }

45         work();//对每一行累加结果

46     }

47     cout<<ans;

48 }

（单调栈其实不好想啊，难点在于推公式，公式的意义就是每个点对答案的贡献，公式想到了，自然也能想到用单调栈维护）。

巴特西

洛谷P1950 长方形（单调栈）

最新文章

热门文章