求助悬线法
查看原帖
求助悬线法
385349
KonJAC_xrs楼主2021/9/9 17:34

先放代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
	while (isdigit(ch)) {x=x*10+ch-48; ch=getchar();}
	return x*f;
}

#define max MAX
inline ll MAX(ll a,ll b){return a>b?a:b;}
#define min MIN
inline ll MIN(ll a,ll b){return a<b?a:b;}

const ll nore=100010;
ll n,m;
ll a[nore],l[nore],r[nore],ans=-0x3f3f3f3f;

int main()
{
	n=read(); m=read();
	char ch[5];
	for(register ll i=1;i<=n;i++)
	{
		//一开始自己想的是每格都悬线 后来发现不用 扫描一排就好了
		for(register ll j=1;j<=m;j++)
		{
			cin>>ch;
			if(ch[0]=='F') a[j]++;//向上扩展 作为该列的悬线高度
			else if(ch[0]=='R') a[j]=0;
		}
		for(register ll j=1;j<=m;j++)
			l[j]=r[j]=j;
		for(register ll j=1;j<=m;j++)
			while(l[j]>=1 and a[j]<=a[l[j]-1])
				l[j]=l[l[j]-1];
		for(register ll j=m;j>=1;j--)	
			while(r[j]<=m and a[j]<=a[r[j]+1])
				r[j]=r[r[j]+1];
		for(register ll j=1;j<=m;j++)
			ans=max(ans,a[j]*(r[j]-l[j]+1));
	}
	cout<<ans*3<<endl;
	return 0;
}

我的疑问是在43,44行的a[j]<=m。

如果改成!=m就对了,但<=就不对。

<=m的情况下输入到

5 6 
R F F F F F 

调试就会卡在44行。

可我感觉这两种都是一样的,求dalao指导。

2021/9/9 17:34
加载中...