洛谷 P1950 长方形_NOI导刊2009提高（2）

传送门

思路

首先定义\(h\)数组，\(h[i][j]\)表示第\(i\)行第\(j\)列最多可以向上延伸多长（直到一个被用过的格子）

然后使用单调栈算出 \(l_i\)和 \(r_i\) ，分别是 \(h[i]\) 中左边第一个（从 \(h[i][j]\) 开始）不大于\(h[i][j]\)的数和右边第一个（从\(h[i][j]\)开始）小于\(h[i][j]\)的数

最终答案为\(ans +=\ (j - l[j]) * (r[j] - j) * h[i][j]\)

即在当前行i中，左边在\(l[j]\)到\(j\)之间任选位置，右边在\(j\)到\(r[j]\)之间任选位置，相乘便得到了底边的方案，高的方案是\(h[i][j]\)，所以再乘\(h[i][j]\)

代码

//知识点:单调栈 
/*
By:Loceaner
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

const int N = 1e3 + 11;

int n, m, h[N][N], st[N], l[N], r[N], top = 0;
char a[N][N];
long long ans;

inline void work(int x) {
    top = 0;
    for(int i = 1; i <= m; ++i) {
        while(top && h[x][st[top]] >= h[x][i]) {
            r[st[top--]] = i;
        }
        st[++top] = i;
    }
    while(top) r[st[top--]] = m + 1;
    for(int i = m; i >= 1; --i) {
        while(top && h[x][st[top]] > h[x][i]) {
            l[st[top--]] = i;
        }
        st[++top] = i;
    }
    while(top) l[st[top--]]=0;
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == '*') h[i][j] = 0;
            else h[i][j] = h[i - 1][j] + 1;
        }
    }
    for(int i = 1; i <= n; i++) {
        work(i);
        for(int j = 1; j <= m; j++) {
            ans += (j - l[j]) * (r[j] - j) * h[i][j];
        } 
    }
    cout << ans << '\n';
    return 0;
}