警示悬线法789wa的后人
  • 板块P4147 玉蟾宫
  • 楼主JackcreaM
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/21 18:17
  • 上次更新2023/11/21 20:12:54
查看原帖
警示悬线法789wa的后人
54465
JackcreaM楼主2023/11/21 18:17

直接看注释即可

#include<bits/stdc++.h>
#define M 1024
using namespace std;//使用悬线法解决luogu P4147 玉蟾宫
int a[M][M];//用来储存地图
int h[M][M];//用来储存每个点的最大高度
int l[M][M];//用来储存每个点最左距离
int r[M][M];//用来储存每个点最右距离
int main()
{
	int n, m, i, j, k;
	cin >> n >> m;
	for (i = 1;i <= n;i++)
	{
		for (j = 1;j <= m;j++)
		{
			char c;
			cin >> c;
			if (c == 'F')//F表示能够覆盖的地方
			{
				a[i][j] = 1;
			}
		}
	}
	for (i = 1;i <= n;i++)//对高度h进行打表
	{
		for (j = 1;j <= m;j++)
		{
			if (a[i][j] == 1)//表示能去
			{
				h[i][j] = h[i - 1][j] + 1;
			}
			else
			{
				h[i][j] = 0;
			}
		}
	}
	for (i = 1;i <= n;i++)//当前格子最左
	{
		for (j = 1;j <= m;j++)
		{
			if (a[i][j] == 1)//表示能去
			{
				l[i][j] = l[i][j - 1] + 1;///为什么不能在这里改呢?因为提前对l[i][j]的改动会影响到l[i][j+1]的赋值!因为我们要找的是当前行的最左障碍与当前点的距离,所以不能提前和l[i-1][j]比较。
				//if (a[i - 1][j] == 1)//上一行能去         
				//{
				//	l[i][j] = min(l[i][j], l[i - 1][j]);
				//}              
			}
			else continue;//跳过这个格子
		}
	}
	for (i = 1;i <= n;i++)//当前格子最右
	{
		for (j = m;j >= 1;j--)
		{
			if (a[i][j] == 1)
			{
				r[i][j] = r[i][j + 1] + 1;
			}
			else continue;
		}
	}
	for (i = 1;i <= n;i++)
	{
		for (j = 1;j <= m;j++)
		{
			if (a[i][j] == 1)
			{
				if (a[i - 1][j] == 1)
				{
					l[i][j] = min(l[i][j], l[i - 1][j]);
					r[i][j] = min(r[i][j], r[i - 1][j]);
				}
			}
		}
	}
	int ans = 0;
	for (i = 1;i <= n;i++)
	{
		for (j = 1;j <= m;j++)
		{
			ans = max(ans, h[i][j] * (l[i][j] + r[i][j] - 1));
		}
	}
	cout << 3 * ans << endl;
	return 0;
}
2023/11/21 18:17
加载中...