题解 P1191 【矩形】

· · 题解

本蒟蒻只会n^3

唉，还是太弱了，靠刷点水题过日子

思路：

我们枚举出矩形左下角的点，坐标为(i,j)，并且枚举这个点向右的长度k，那么以(i,j)为左下角，宽度为k-j+1的矩形自然就是能向上扩展的高度最小值了，光说可能不太清楚，下面模拟一下（有图哦qwq）

我们以下面为例子，粗略讲一下（不会全部模拟）

样例：

4 WWWW WWBW WWWW WWWW

那么假设我们枚举i,j分别为4,1，也就是第四行第一列，那么我们向右枚举k

当k=1时，我们求出以i,j为左下角，宽度为k-j+1也就是1的矩形有多少个，我们可以看到有4个，分别是:

我们其实可以发现就是能向上扩展的高度个矩形

当k=2时,我们发现以i,j为左下角，宽度为2的矩形也有4个，分别为：

当k=3时，我们发现以i,j为左下角，宽度为3的矩形有2个，分别为：

当k=4时，我们发现以i,j为左下角，宽度为4的矩形有2个，分别为：

那么到这里我们就枚举出了左下角为4,1的所有矩形

而且我们可以发现，矩形个数就是能向上扩展的高度

那么我们会枚举i,j，让每一个点作为矩形左下角，同时枚举宽度，一层一层下来，最后就是不遗漏的所有矩形个数，具体证明就省略了，自己想想就知道了

时间复杂度O(n^3)

下面是美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 157
using namespace std;
int n,now,ans;
int high[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            char in;
            scanf(" %c",&in);
            if(in=='W')
                ++high[j];
            else
                high[j]=0;
        }
        for(int j=1;j<=n;++j)
        {
            now=high[j];
            for(int k=j;k<=n;++k)
            {
                if(!high[k])
                    break;
                now=min(now,high[k]);
                ans+=now;
            }
        }
    }
    printf("%d",ans);
    return 0;
}