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

题目描述

小明今天突发奇想，想从一张用过的纸中剪出一个长方形。

为了简化问题，小明做出如下规定：

（1）这张纸的长宽分别为n，m。小明讲这张纸看成是由n*m个格子组成，在剪的时候，只能沿着格子的边缘剪。

（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。

（3）剪出来的长方形的大小没有限制。

小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？

输入格式

第一行两个正整数n，m，表示这张纸的长度和宽度。

接下来有n行，每行m个字符，每个字符为“*”或者“.”。

字符“*”表示以前在这个格子上画过，字符“.”表示以前在这个格子上没画过。

输出格式

仅一个整数，表示方案数。

输入输出样例

输入 #1

6 4
....
.
...
.
...
.***

输出 #1

38

说明/提示

【数据规模】

对10%的数据，满足1<=n<=10,1<=m<=10

对30%的数据，满足1<=n<=50,1<=m<=50

对100%的数据，满足1<=n<=1000,1<=m<=1000

【思路】

单调队列
先输入数据
处理处每个点往上一共有多少个连续的没有被画过的点
然后每一行f[i][0]和f[i][m + 1]要赋值一个超级小的数
为了让区间边界终止与此

然后顺序扫一遍找出每一个点
左边距离他最近的一个比他矮的点
然后倒叙扫一遍找出每一个点
右边距离他最近的一个比他矮的店
中间的就是它能够构成的矩阵
矩阵组成方式是
左边区间的长度（包括中间点） * 右边区间的长度（包括中间点） * 宽（也就是f[i][j]）
累加起来输出就好了

要开long long 哦不然最后两个点过不了

【完整代码】

#include<iostream>
#include<cstdio>
#include<stack>
#define int long long

using namespace std;
const int Max = 1005;
int f[Max][Max];
int a[Max]; 
int r[Max],l[Max];
signed main()
{
    char c;
    int n,m;
    cin >> n >> m;
    for(register int i = 1;i <= n;++ i)
    {
        for(register int j = 1;j <= m;++ j)
        {
            cin >> c;
            if(c == '*')f[i][j] = 0;
            else
            f[i][j] = f[i - 1][j] + 1;
        }
    }
    for(int i = 1;i <= n;++ i)
        f[i][0] = f[i][m + 1] = -0x7fffffff;
    int ans = 0;
    for(register int i = 1;i <= n;++ i)
    {
        stack<int>s1,s2;
        s1.push(1),s2.push(m);
        for(register int ii = 2,jj = m - 1;ii <= m + 1,jj >= 0;jj --,++ ii)
        {
            while(!s1.empty() && f[i][ii] < f[i][s1.top()])
            {
                r[s1.top()] = ii;
                s1.pop();
            }
            while(!s2.empty() && f[i][jj] <= f[i][s2.top()])
            {
                l[s2.top()] = jj;
                s2.pop();
            }
            s1.push(ii);s2.push(jj);
        }
        for(register int j = 1;j <= m;++ j)
            ans += (j - l[j]) * (r[j] - j) * f[i][j];
    }
    cout << ans << endl;
    return 0;
}

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

原文：https://www.cnblogs.com/acioi/p/11650763.html