n方的做法。。。这么恐怖
by iodwad @ 2017-12-11 21:53:15
好像是有的
by cszmc2004 @ 2018-02-04 12:13:19
有，悬线算法即可(可以去看棋盘制作那一题)
by GuessYCB @ 2018-02-04 12:31:08
有，单调栈做法。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,top;
int drp[N],s[N];
long long ans,f[N];
char a[N][N];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%s",a[i]+1);
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
if(a[i][j]=='B') drp[j]=i;
while(top && drp[s[top]]<=drp[j]) top--;
f[j]=f[s[top]]+1LL*(j-s[top])*(i-drp[j]);
s[++top]=j;
}
for(int j=1; j<=n; ++j) ans+=f[j], f[j]=0;
top=0;
}
printf("%lld\n",ans);
return 0;
}
```
by nosta @ 2018-09-19 12:05:21
@[AK_583](/space/show?uid=46749)
单调栈了解一下
by x义x @ 2018-10-26 12:51:36