题解 P1950 【长方形_NOI导刊2009提高（2）】

铃宕 · 2019-02-18 22:16:17 · 题解

使用单调栈求解 O（nm）

update 于 2019-8-11 ~~ 写得很差，建议还没看过的就不要看了 ~~

我们要解决的第一个问题是如何求总方案数

1. 对每一行统计以其为底边构造的长方形的数量(怎么求后面讲)

2. 每行的方案数之和及为总方案数（因为一个长方形不可能有两个底边，所以此方法可以保证不重不漏）

那么怎么求对每一行统计以其为底边构造的长方形的方案数呢？

首先我们了解一下什么是单调栈（不过神犇们都应该会了）

1.定义

单调栈是一种可以以 O(n) 的时间复杂度解决类似求对于每一个数 i 左边（或右边）第一个（从 i 开始）比它小（或大）的数的问题的算法 （语文不好）

下面以求对于每一个数 i 左边第一个（从 i 开始）不大于它的数为例

2. 怎么做？

首先定义一个栈（先进后出）栈中存的是目前还没有答案的数，易得栈中元素递减（不然与栈的定义不符），对于每一次要将元素压入栈，先将栈顶所有大于它的元素记录答案（就是要压入的元素）并弹出，因为我们要求左边第一个，所以以从右向左的顺序入栈（因为是先入栈再记录答案，所以要从元素从答案入栈）

//代码，单调栈
void ddzl(){
    top=0;//清空栈
    for(int i=m;i>=1;i--){
        while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;//记录答案
        top++;
        k[top]=i;//入栈
    }
    while(top) l[k[top]]=0,top--;//对没有答案做特殊处理
}

扯了一堆，是时候说如何统计以其为底边构造的长方形的方案数了

1. 定义 h_i 为当前行第 i 列可向上延伸多少（即有多少为图画的块，如果当前块被图画那么值为0）

2. 使用单调栈算出 l_i 和 r_i ，分别是 h 中左边第一个（从 h_i 开始）不大于 h_i 的数和右边第一个（从 h_i 开始）小于 h_i 的数

3. 对每一列求出被这一列的高度限制的长方形数，即为(i - l_i)\times(r_i - i)\times h_i 将所有列的答案相加就是以当前行为底边构造的长方形的方案数了

为什么第3步不会重复： 有重复是只有一种情况，即当 l_i 到 r_i 之间有一个 j 使 h_j 小于 h_i ，但是这是不可能的，因为l_i 和 r_i 分别是 h 中左边第一个（从 h_i 开始）不大于 h_i 的数和右边第一个（从 h_i 开始）小于 h_i 的数，所以在 l_i 到 r_i 之间不存在 j 使 h_j 小于 h_i

举个例子：

对于某条情况如下图的底边
（0为没图画，1为有图画）
     0 1 0 1 0 0
     1 0 1 0 1 0
     1 0 0 1 0 0
     1 0 1 0 0 0
   h:0 3 0 1 2 4
   l:0 1 0 3 4 5
   r:7 3 7 7 7 7
方案：0 3 0 3 4 4
总方案数：14，验算后发现没错

update:

关于一些问题的解答：

Q1：为什么公式是这样的呢？

解答： 对于每次求方案数，我们要先选底边（叫底边好像不太合理，凑合着看吧），由于我们是要求被这一列的高度限制的长方形数，所以底边必须包含这一列，那么底边左端点的方案数即为 i - l_i，同理右端点的方案数为 r_i - i，底边的方案数即为(i - l_i)\times(r_i - i)，而高的方案数则为 h_i (不要理会这个称呼)，所以公式就是 (i - l_i)\times(r_i - i)\times h_i

Q2: 为什么 l_i , r_i 是一个不大于，一个小于呢?

解答：一个不大于，一个小于是因为如果有相邻的且 h_i 相等 的，两个都是不大于会有重复，而两个都是小于有会有一些长方形没数到，而,一个不大于，一个小于是相当于去了重复的

时间复杂度

code

#include<bits/bycx++.h>
using namespace std;
char ch;
long long l[1020],r[1020],h[1020],k[1020],n,m,top;
int d[1020][1020];
long long ans;
void ddzl(){//单调栈，前面的代码有注释
    top=0;
    for(int i=m;i>=1;i--){
        while(top!=0&&h[i]<=h[k[top]]) l[k[top]]=i,top--;
        top++;
        k[top]=i;
    }
    while(top) l[k[top]]=0,top--;
}
void ddzr(){//同上
    top=0;
    for(int i=1;i<=m;i++){
        while(top!=0&&h[i]<h[k[top]]) r[k[top]]=i,top--;
        top++;
        k[top]=i;
    }
    while(top) r[k[top]]=m+1,top--;
}
void work(){
    ddzl();
    ddzr();//两次单调栈预处理l，r
    for(int i=1;i<=m;i++){
        ans+=(i-l[i])*(r[i]-i)*h[i];//统计
    } 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){//输入
        for(int j=1;j<=m;j++){
            cin>>ch;
            if(ch=='*') d[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){h[j]++;if(d[i][j]) h[j]=0;}//预处理h
        work();统计当前行
    }
    cout<<ans;//输出
//} 不要抄代码

头文件防抄袭

有问题请私信作者