题意:链接方法:最大子矩阵之算♂法②解析:首先这道题单调栈DP是肯定能过的，但是一点都不高端！什么年代了还用这种方式！所以如何彰显自己是个高端的人呢？悬线法能满足你的需求！什么是悬线法？首先对于悬线的定义，对于一个n*m的坐标图中的任意一点，其向上能延伸的一个线段(不碰到坏点)称为悬线。如果定义h[i,j]代表(i,j)该点的悬线长度。那么，如果其上方的点是坏点，则悬线长度为0，该点为坏点，悬线长度为0，否则的话，为上方的点的悬线长度加1。如果这么统计的话，那么最终的悬线长度应该为h[i,j]+1,不清楚自行观察。然后呢对于一个悬线，我们欲知道最大子矩阵的大小的时候，需要将该悬线平移，即其向左能平移多长距离，向右能平移多长距离，不妨令l[i,j]为向左平移多少距离，r[i,j]为向右平移多长距离，便于统计，我们将坏点的这两种值置为0，非坏点的l为前1点+1，r为后一点+1，最终的l+r-1即为该矩阵的长，又悬线为宽，所以面积可以拿出。但是怎么实现呢？首先我们先假设所有的l,r都是对于本行的，那么很容易的就能处理出来所有点的l,r。复杂度2nm之后我们枚举所有的非坏点，在更新h的同时，，更新l,r，很容易发现，当前点的l应该是其上方的点的l与该点在其本行的l的较小者。不妨假设悬线长为2，那么随便画个图就能知道。悬线长大于2呢？又是个递归思想。r的处理同理。那么最终所有点的(h+1)*(l+r-1)就是该点对应的最大子矩阵面积。可能有人会说，这样的话下边界不是最远距离啊？但是别忘了，我们是按次序枚举的，也就是说，最远的下边界上的点我们一定会枚举到，在该点时便会更新。这个算法与①有什么区别呢？它的复杂度为n*m，在图较小的时候显然适合这种方法。代码:;int l,w;int h[N][N];int le[N][N];int ri[N][N];int map[N][N];char s[2];int main(){scanf(“%d%d”,&l,&w);for(int i=1;i<=l;i++){for(int j=1;j<=w;j++){scanf(“%s”,s);if(s[0]==’F’)map[i][j]=1;}}for(int i=1;i<=l;i++){for(int j=1;j<=w;j++){if(!map[i][j])le[i][j]=0;else le[i][j]=le[i][j-1]+1;}for(int j=w;j>=1;j–){if(!map[i][j])ri[i][j]=0;else ri[i][j]=ri[i][j+1]+1;}}for(int i=1;i<=l;i++){for(int j=1;j<=w;j++){if(map[i-1][j]&&map[i][j]){h[i][j]=h[i-1][j]+1;le[i][j]=min(le[i][j],le[i-1][j]);ri[i][j]=min(ri[i][j],ri[i-1][j]);}}}int ans=0;for(int i=1;i<=l;i++){for(int j=1;j<=w;j++){ans=max(ans,(h[i][j]+1)*(le[i][j]+ri[i][j]-1));}}printf(“%d\n”,ans*3);}
版权声明：本文为博主原创文章，未经博主允许不得转载。
最有效的资本是我们的信誉，它24小时不停为我们工作。
