洛谷4147 玉蟾宫

原题链接

和 [ZJOI2007]棋盘制作（题解）基本一样。
这里是用单调栈来做的，悬线法可参考我在棋盘制作所用的。
初始化出矩阵中每一列连续的(F)的最大长度。

//例 
R F F F F F      0 1 1 1 1 1
F F F F F F      1 2 2 2 2 2
R R R F F F ---> 0 0 0 3 3 3
F F F F F F      1 1 1 4 4 4
F F F F F F      2 2 2 5 5 5

于是，我们就可以对每一行都跑一遍单调栈，对答案不断取(max)即可。
简单说下单调栈，这里要维护的是一个递增的单调栈。

1. 若该矩阵的高度大于等于栈顶矩阵高度，直接入栈，并将宽度设为(1)。
2. 若该矩阵的高度小于栈顶矩阵高度，则不断弹出栈内矩阵，并累计它们的长度，同时计算面积，即当前累计的长度乘上当前弹出的矩阵的高度，对其与答案取(max)，当栈顶矩阵的高度小于等于要入栈的矩阵时，再将其入栈，并将其宽度设为之前弹出矩阵时累计的宽度(+1)（因为那些矩阵的高度都比它高，所以可以累计到它的宽度中）。

另外，设一个编号为(n + 1)、高度为(0)的矩阵，以将栈内剩余的矩阵全部弹出，并计算面积取(max)。

#include<cstdio>
using namespace std;
const int N = 1010;
int a[N][N], sta[N], W[N], tp;
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c < '0' || c > '9'; c = getchar())
		p |= c == '-';
	for (; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + c - '0';
	return p ? -x : x;
}
inline int re_l()
{
	char c = getchar();
	for (; c ^ 'R' && c ^ 'F'; c = getchar());
	return c ^ 'R' ? 1 : 0;
}
inline int maxn(int x, int y)
{
	return x > y ? x : y;
}
int main()
{
	int i, j, n, m, w, tp, ma = 0;
	n = re();
	m = re();
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
		{
			a[i][j] = re_l();
			if (a[i][j])
				a[i][j] = a[i - 1][j] + 1;
		}
	for (tp = 0, i = 1; i <= n; i++, tp = 0)//对每一行跑单调栈
		for (j = 1; j <= m + 1; j++)
		{
			if (sta[tp] <= a[i][j])
			{
				sta[++tp] = a[i][j];
				W[tp] = 1;
			}
			else
			{
				w = 0;
				for (; sta[tp] > a[i][j]; tp--)
				{
					w += W[tp];
					ma = maxn(ma, w * sta[tp]);
				}
				sta[++tp] = a[i][j];
				W[tp] = w + 1;
			}
		}
	printf("%d", ma * 3);
	return 0;
}