没用单调队列,自测对,上传0
查看原帖
没用单调队列,自测对,上传0
637338
Fengman楼主2022/7/11 18:16

本地和题解对拍半天没找出错,甚至比题解快。 哪位大佬能看看。

#include<cstdio>

using namespace std;

long long xd[2001][2001],fz;
bool a[2001][2001];
char shu;
long long ans;
int n,m;
//a 判断是不是杂草
//shu 用来输入
//xd 线段,存以此点为左端点的横向边最长有多长
//fz 辅助枚举矩阵大小

int main()
{
	scanf("%d%d",&n,&m);
	getchar();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			shu=getchar();
			if(shu=='.')
			{
				a[i][j]=true;
				fz=j;
				while(fz&&a[i][fz])
					xd[i][fz--]++;
			}
		}
		getchar();
	}//输入+预处理横向边长度

------------

//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)	
//		{
//			if(a[i][j])
//				printf("%d ",xd[i][j]);
//			else
//				printf("#");
//		}
//		printf("\n");
//	}//检验代码
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			//枚举点
			if(a[i][j])
			{
				for(int c=1;c<=xd[i][j];c++)
				{//枚举矩阵长
					int k=1;
					while(i-k>=0&&xd[i-k+1][j]>=c)//枚举矩阵宽,不能超出范围&&要能放下矩阵
					{
//	printf("%d  %d || %d %d%d\n",i,j,c,k,c*k);
						ans+=k*c;//加上矩阵大小
						k++;
					}
				}	
			}
			
		}
	}
	printf("%lld",ans);//输出
	return 0;
}
2022/7/11 18:16
加载中...