玄3*关求助
  • 板块P1191 矩形
  • 楼主StarsTwinkle
  • 当前回复9
  • 已保存回复10
  • 发布时间2024/1/21 21:08
  • 上次更新2024/1/22 09:07:14
查看原帖
玄3*关求助
1267405
StarsTwinkle楼主2024/1/21 21:08

#1 15

Local output 0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=155;
int n,m,ans=0;
int up[N][N],stk[N],top,rht[N],lft[N];
int main()
{
    char a;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a;
            if(a=='W')up[i][j]-up[i-1][j]+1;
            else up[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){//固定下边界
        top=0;
        for(int j=1;j<=n;j++){//求右边第一个小于本身高度的位置
            while(top>0&&up[i][j]<up[i][stk[top]]){
                rht[stk[top]]=j;
                top--;
            }
            top++;
            stk[top]=j;
        }
        while(top>0){
            top--;
            rht[stk[top]]=n+1;
        }
        for(int j=1;j<=n;j++){//求左边第一个小于或者等于本身高度的位置
            while(top>0&&up[i][stk[top]]>up[i][j]){
                top--;
            }
            if(top>0){
                lft[j]=stk[top];
            }
            else{
                lft[j]=0;
            }
            top++;
            stk[top]=j;
        }
        for(int j=1;j<=n;j++){//穷举所有中心线
            ans+=(j-lft[j])*(rht[j]-j)*up[i][j];
        }
    }
    cout<<ans;
	return 0;
}
2024/1/21 21:08
加载中...