悬线法用于找出矩阵中满足特定条件的最大的矩形
说实话,像这种P4147 玉蟾宫这样的题我本来是用从上而下向下找最大值的方法(有点像悬线法,但要麻烦一点),又看了一遍题解,发现了悬线法这种比较容易理解的做法
悬线法的思想很简单,就是记录每个点向上延伸的最大长度,再算出延伸这么长时最左和最右的长度,然后相乘即可。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF=1e9+7,MAXN=1010; int N,M,ans,a[MAXN][MAXN],up[MAXN][MAXN],lft[MAXN][MAXN],rt[MAXN][MAXN]; int main(){ scanf("%d %d",&N,&M);//读入 for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ char ch; scanf(" %c",&ch); a[i][j]=ch=='F';//判断是否是'F',用a存储领地 } } for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ if(a[i][j]==1){//如果是'F' up[i][j]=up[i-1][j]+1;//处理上,如果i是1也没事,因为数组从1开始,那么a[0][0]=1 lft[i][j]=lft[i][j-1]+1;//处理左,如果左边是‘F’就从左边基础+1,类似dp } if(a[i][M-j+1]){//这里是从右开始检索,因为这样可以减少一次循环,超划算 rt[i][M-j+1]=rt[i][M-j+2]+1;//注意+1和+2,处理右 } } } for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ if(a[i][j]&&a[i-1][j]){//如果都是'F' lft[i][j]=min(lft[i][j],lft[i-1][j]);//特别注意,要找到这个矩形从上到下最小的左值,要不然一味 //找最大值会不满足其他行的条件,比如4行lft是4,但3行是1,那么选4的话,3不就凹进去了吗 rt[i][j]=min(rt[i][j],rt[i-1][j]);//同左边的道理 } ans=max(ans,(rt[i][j]+lft[i][j]-1)*up[i][j]);//计算面积 } } printf("%d",3*ans);//别忘了*3(题中所求)!! return 0; }
这篇代码来自https://www.cnblogs.com/guoshaoyang/p/11296004.html,我的码风太丑,不配,稍微加了些注释
说实话没有大佬指点自己理解真的很难,以上差不多为悬线法的板子题,当然可能与他人不一样,有些人可能是通过右减左来达到目的,不过思路是一样的
同样的题还有P1169 [ZJOI2007]棋盘制作,可以做一做巩固一下
感谢观看