P4147 玉蟾宫
原本是想做棋盘制作的，发现有种什么方法叫做悬线法。
并且听说这个题算是到板子题。然后就学习了一发
emmmm
上面是《浅谈用极大化思想解决最大子矩形问题》
~~然而第一种根据障碍点的算法并没有看懂qwq ~~
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using std::min;
using std::max;
const int maxn=1010;
int GET()
{char c=getchar();while(c!='R'&&c!='F') c=getchar();return c == 'R' ? 0 : 1;
}
int M[maxn][maxn];//给定的图
int l[maxn][maxn],r[maxn][maxn];//某个点能向左向右拓展到的下标
int L[maxn][maxn],R[maxn][maxn];//某条悬线能向左向右拓展到的下标
int h[maxn][maxn];//悬线的高度
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)M[i][j]=GET();for(int i=1;i<=n;i++)//预处理每个点能拓展的数值{int t=0;//最近一次障碍的位置for(int j=1;j<=m;j++)if(M[i][j]) l[i][j]=t+1;//标记else L[i][j]=0,t=j;//t更新，至于为什么L[i][j]要置为0，考虑在递推悬线的时候，如果一个点的上面是障碍，那么这个天限制他向左拓展的点只有他左边的障碍，所以这里为了不影响这种情况，遂置极小数t=m+1;for(int j=m;j>=1;j--)if(M[i][j]) r[i][j]=t-1;else R[i][j]=m+1,t=j;//同理}for(int i=1;i<=m+1;i++) R[0][i]=m+1;//将上面封死，原理同上for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(M[i][j]){h[i][j]=h[i-1][j]+1;//悬线长+1L[i][j]=max(L[i-1][j],l[i][j]);//在左边取一个下标最大的障碍R[i][j]=min(R[i-1][j],r[i][j]);//在右边取一个下标最小的障碍}int ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=max(ans,(R[i][j]-L[i][j]+1)*h[i][j]);//枚举每条悬线，进行计算printf("%d",3*ans);
}