P4147 玉蟾宫

悬线法预处理 dp。

神级实现。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1005
char s[3];
int n, m, a[N], l[N], r[N];
signed main()
{
	int ans = 0;
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			scanf("%s", s);
			if(s[0] == 'R')
			{
				a[j] = 0;
			}
			else if(s[0] == 'F')
			{
				a[j]++;
			}
		}
		for(int j = 1; j <= m; j++)
		{
			if(j == 1)
			{
				l[j] = 1;
				continue;
			}
			int pos = j - 1;
			for(; pos >= 1; pos--)
			{
				if(a[j] > a[pos])
				{
					break;
				}
				else
				{
					pos = l[pos];
				}
			}
			l[j] = pos + 1;
		}
		for(int j = m; j >= 1; j--)
		{
			if(j == m)
			{
				r[j] = m;
				continue;
			}
			int pos = j + 1;
			for(; pos <= m; pos++)
			{
				if(a[j] > a[pos])
				{
					break;
				}
				else
				{
					pos = r[pos];
				}
			}
			r[j] = pos - 1;
		}
		for(int j = 1; j <= m; j++)
		{
			ans = max(ans, a[j] * (r[j] - l[j] + 1));
		}
	}
	printf("%lld", ans * 3);
	return 0;
}