传送门

题意

给出一个矩阵，上面是可以用的土地和不能用的土地，要在上面选一块矩形的土地建房子，问最大能选多大的土地，土地每单位3块大洋，最后输出租金

分析

这道题跟杭电多校的第一场一样，都是转换成模型然后用悬线法进行求解即可
我们可以把 i , j i,j i,j位置向上有多少个格子是满足要求的处理出来为 a [ i ] [ j ] a[i][j] a[i][j]，然后一行一行预处理，以 a [ i ] [ j ] a[i][j] a[i][j]为宽度的最大长度 l i , r i l_i,r_i li​,ri​，然后求解即可

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 2010;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
	char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
	while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
int n, m;
int l[N], r[N];
int q[N];
int f[N][N];

int query(int h[]) {
	h[0] = h[m + 1] = -1;
	int tt = -1;
	q[++ tt] = 0;
	for (int i = 1; i <= m; i ++)
	{
		while (h[q[tt]] >= h[i])  tt --;
		l[i] = q[tt] + 1;
		q[++ tt] = i;
	}
	tt = -1;
	q[++ tt] = m + 1;
	for (int i = m; i; i --)
	{
		while (h[q[tt]] >= h[i])  tt --;
		r[i] = q[tt] - 1;
		q[++ tt] = i;
	}
	int res = 0;
	for (int i = 1; i <= m; i ++)  res = max(res, h[i] * (r[i] - l[i] + 1));
	return res;
}

int main() {
	int T;
	read(T);
	while (T--) {
		read(n), read(m);
		char ch[2];
		memset(f, 0, sizeof f);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				scanf("%s", ch);
				if (ch[0] == 'F') f[i][j] = f[i - 1][j] + 1;
				else f[i][j] = 0;
			}
		int ans = 0;
		for (int i = 1; i <= n; i++)
			ans = max(ans, query(f[i]));
		di(ans * 3);
	}

}