单调栈求助
查看原帖
单调栈求助
270854
二叉苹果树楼主2022/10/23 11:17
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
#define MAXN 1005
char ch[MAXN][MAXN];
int n,m,top;
int h[MAXN],l[MAXN],r[MAXN],st[MAXN];
long long ans;
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ch[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            h[j]=ch[i][j]=='*'?0:h[j]+1;
    top=0;
    for(int j=1;j<=m;j++)
    {
        while(top>0&&h[j]<h[st[top]])
        {
            r[st[top]]=j;
            top--;
        }
        top++;
        st[top]=j;
    }
    while(top>0)
    {
        r[st[top]]=m+1;
        top--;
    }
    top=0;
    for(int j=m;j>=1;j--)
    {
        while(top>0&&h[j]<=h[st[top]])
        {
            l[st[top]]=j;
            top--;
        }
        top++;
        st[top]=j;
    }
    while(top>0)
    {
        l[st[top]]=0;
        top--;
    }
    for(int j=1;j<=m;j++)
        ans+=(j-l[j])*(r[j]-j)*h[j];
    cout<<ans<<endl;
    return 0;
}

照着深进抄的。全WA

自查了三遍没找到问题

2022/10/23 11:17
加载中...