C++14(g++5.4) 解法, 执行用时: 22ms, 内存消耗: 5352K, 提交时间: 2020-06-15 11:47:55

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

const ll mod=1000000007;
const int N=1007;

int n,m;
char a[N][N];
int stk[N],cnt[N][N];

int main(){
	ll Ans=0;
	n=input(),m=input();
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
		ll sum=0,top=0;
		for(int j=1;j<=m;j++){
			if(a[i][j]=='O') cnt[i][j]=cnt[i-1][j]+1;
			sum+=cnt[i][j];
			while(top&&cnt[i][stk[top]]>cnt[i][j]){
				sum-=(stk[top]-stk[top-1])*(cnt[i][stk[top]]-cnt[i][j]);
				top--;
			}
			stk[++top]=j;
			Ans=(Ans+sum%mod)%mod;
		}
	}
	printf("%lld\n",Ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 21ms, 内存消耗: 2524K, 提交时间: 2020-06-19 19:16:52

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
char R[1005][1005];
int main()
{
    int i,j,t,n,m,ans=0,DP[1005]={0},h[1005]={0},S[1005]={0};
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%s",R[i]+1);
    for(i=1;i<=n;i++)
    {
		for(t=0,j=1;j<=m;j++)
		{
			if(R[i][j]=='O')h[j]++;
    		else h[j]=0;
			while(t&&h[S[t]]>=h[j])t--;
			DP[j]=(DP[S[t]]+(long long)h[j]*(j-S[t])%mod)%mod;
			ans=(ans+DP[j])%mod,S[++t]=j;
		}
	}
	printf("%d\n",ans);
}