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

题目描述

输入格式

输出格式

最新文章

热门文章