单调栈,为何得0分?样例过了,求助大佬
  • 板块P1950 长方形
  • 楼主mystic_qwq
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/12/25 23:55
  • 上次更新2023/12/26 14:09:16
查看原帖
单调栈,为何得0分?样例过了,求助大佬
246331
mystic_qwq楼主2023/12/25 23:55
#define MAX 1002
char ch[MAX];
short n,m,h[MAX],l[MAX],r[MAX],st[MAX];
long long ans;
main(){
  scanf("%d%d",&n,&m),++n;
  while(n--){
    gets(ch+1);
    for(int i=1;i<=m;++i)
      h[i]=ch[i]=='.'?h[i]+1:0;
    for(int i=1,top=0;i<=m+1;++i){
      while(top&&h[i]<h[st[top]])
        r[st[top--]]=i;
      st[++top]=i;
    }
    for(int i=m,top=0;~i;--i){
      while(top&&h[i]<=h[st[top]])
        l[st[top--]]=i;
      st[++top]=i;
    }
    for(int i=1;i<=m;++i)
      ans+=(i-l[i])*(r[i]-i)*h[i];
  }
  printf("%ld",ans);
}

2023/12/25 23:55
加载中...