大家好，欢迎来到IT知识分享网。
一道单调栈的好题啊。。。。。。
思路是很奇妙的，对于每个点（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 }
（单调栈其实不好想啊，难点在于推公式，公式的意义就是每个点对答案的贡献，公式想到了，自然也能想到用单调栈维护）。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/33505.html
