luogu P1191 矩形 |dp

题目描述

给出一个n×nn \times nn×n的矩阵，矩阵中，有些格子被染成白色，有些格子被染成黑色，现要求矩阵中白色矩形的数量

输入格式

第一行，一个整数nnn，表示矩形的大小。

接下来nnn行，每行nnn个字符，这些字符为“WWW”或“BBB”。其中“WWW”表示白格，“BBB”表示黑格。

输出格式

一个正整数，为白色矩形数量

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=155;
#define int long long
char c[N][N];
int cnt[N];
signed main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        cin>>c[i][j];
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            if(c[i][j]=='B')cnt[j]=0;
            else cnt[j]++;
        for(int j=1;j<=n;j++){
            int high=cnt[j];
            for(int k=j;k<=n;k++){
                if(!cnt[k])break;
                high=min(high,cnt[k]);
                ans+=high;
            }
        }
    }
    cout<<ans<<endl;
}

luogu P1191 矩形 |dp

原文：https://www.cnblogs.com/naruto-mzx/p/11895626.html