为什么这题O(n^3)的算法也能过?
  • 板块P1950 长方形
  • 楼主STUDENT00
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/10/6 18:31
  • 上次更新2023/10/27 08:27:15
查看原帖
为什么这题O(n^3)的算法也能过?
658786
STUDENT00楼主2022/10/6 18:31

RT,代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,s[1010][1010];
long long dp[1010][1010],ans;
char c[1010][1010];
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++) scanf("%s",c[i]+1);
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			if(c[i][j]=='*') s[i][j]=0;
			else s[i][j]=s[i][j-1]+1; 
		}
	}
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=m;j++){
			int mins=1e9;
			for(register int k=i;k>=1;k--){
				if(s[k][j]){
					mins=min(mins,s[k][j]);
					dp[i][j]+=mins;
				}else break;
			}
			ans+=dp[i][j];
		}
	}
	printf("%lld",ans);
	return 0;
}
2022/10/6 18:31
加载中...