同样悬线法,为什么我wa的是8,9,10
  • 板块P4147 玉蟾宫
  • 楼主yzzxljxx
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/3 17:15
  • 上次更新2024/9/3 21:45:00
查看原帖
同样悬线法,为什么我wa的是8,9,10
1077738
yzzxljxx楼主2024/9/3 17:15
#include<bits/stdc++.h>
using namespace std;
const int Max = 1e3 + 5;
int matrix[Max][Max];
int up[Max][Max];
int ld[Max][Max];
int rd[Max][Max];

int main()
{
	int n, m;
	char temp;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)//先读取
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> temp;
			if (temp == 'R')
			{
				matrix[i][j] = 1;
			}
			else if (temp == 'F')
			{
				matrix[i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= n; i++)//求出高度
	{
		for (int j = 1; j <= m; j++)
		{
			if (matrix[i][j])
			{
				continue;
			}
			up[i][j] = up[i - 1][j] + 1;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		stack<int> righting;
		for (int j = m; j >= 1; j--)
		{
			if (!righting.empty() and up[i][righting.top()] >=up[i][j])
			{
				righting.pop();
			}
			if (!righting.empty())
			{
				rd[i][j] = righting.top() - j-1;
			}
			else
			{
				rd[i][j] = m - j;
			}
			righting.push(j);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		stack<int> lefting;
		for (int j = 1; j <= m; j++)
		{
			if (!lefting.empty() and up[i][lefting.top()] >= up[i][j])
			{
				lefting.pop();
			}
			if (!lefting.empty())
			{
				ld[i][j] = j - lefting.top() -1;
			}
			else
			{
				ld[i][j] = j - 1;
			}
			lefting.push(j);
		}
	}
	int ans = 0;
	int s;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			s = (rd[i][j] + ld[i][j] + 1) * up[i][j];
			if (s > ans)
			{
				ans = s;
			}
		}
	}
	cout << ans*3;

	return 0;
}

我的思路就是对于每个点都用两次单调栈算出左右两边第一个小于当前高度的格子,然后求面积,如果那个点是R,由于高度为0,所以在计算面积时候不会影响 我看了好多求助帖,大家都是789但是我过了7结果10死掉了

2024/9/3 17:15
加载中...