悬线法(知识点总结)

暑假学的&＃xff0c;当时也没总结&＃xff0c;今天又看到&＃xff0c;怕再忘了吧……

其实就还是dp的思想&＃xff0c;搞来搞去这个样子……

思路来源

https://blog.csdn.net/qq_30358129/article/details/88044727

最大01子矩阵

题目可以用来交poj3494

h[i][j]表示以(i,j)为最下位置的悬线的高度&＃xff0c;

l[i][j]表示(i,j)能拓到的最左位置&＃xff0c;r[i][j]代表(i,j)能拓到的最右位置

枚举每一行&＃xff0c;然后如果上一行有值的话就将同行子矩形变窄&＃xff0c;否则不变

以上思想即可解决最大01子矩阵问题&＃xff0c;然后单调栈也可以解决

#include
#include
using namespace std;
const int N&＃61;2e3&＃43;10;
int m,n,a[N][N],l[N][N],r[N][N],h[N][N];
int main()
{while(~scanf("%d%d",&n,&m)){for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){scanf("%d",&a[i][j]);}}int L&＃61;1e9,R&＃61;0,ans&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){if(a[i][j]&＃61;&＃61;1)L&＃61;min(L,j);//尺取连续段最左1的位置 else L&＃61;1e9;l[i][j]&＃61;L;}for(int j&＃61;m;j>&＃61;1;--j){if(a[i][j]&＃61;&＃61;1)R&＃61;max(R,j);//尺取连续段最右1的位置 else R&＃61;0;r[i][j]&＃61;R; }for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){if(a[i-1][j]){h[i][j]&＃61;h[i-1][j]&＃43;1;l[i][j]&＃61;max(l[i-1][j],l[i][j]);//收左线r[i][j]&＃61;min(r[i-1][j],r[i][j]);//收右线 }else h[i][j]&＃61;1;if(a[i][j])ans&＃61;max(ans,(r[i][j]-l[i][j]&＃43;1)*h[i][j]);}}printf("%d\n",ans);}return 0;
}

最大同色子矩阵

魔改一下悬线法&＃xff0c;把相同颜色的抠出来&＃xff0c;考虑什么时候修改l[]和r[]的值

代码将h[j]不更新时初始化为极小/极大&＃xff0c;从而将取max和取min对l[]和r[]的修改统一

相同的思想在于&＃xff0c;如果上面可以继承&＃xff0c;就一定会缩左界和右界&＃xff0c;代表悬线必取的左右界

如果仍用单调栈的话&＃xff0c;需要套一个尺取

#include
#include
using namespace std;
const int N&＃61;2e3&＃43;10;
typedef long long ll;
int m,n,a[N][N];
int l[N],r[N],h[N];
int main()
{while(~scanf("%d%d",&n,&m)){for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){scanf("%d",&a[i][j]);}}for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)l[j]&＃61;0,r[j]&＃61;m&＃43;1,h[j]&＃61;0;ll ans&＃61;0;int la,ra;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){la&＃61;0;ra&＃61;m&＃43;1;for(int j&＃61;1;j<&＃61;m;&＃43;&＃43;j){if(a[i][j]&＃61;&＃61;a[i-1][j])h[j]&＃43;&＃43;;else h[j]&＃61;1,l[j]&＃61;0,r[j]&＃61;m&＃43;1;if(a[i][j]&＃61;&＃61;a[i][j-1])l[j]&＃61;max(l[j],la&＃43;1);else l[j]&＃61;j,la&＃61;j-1;//考虑到l[j]<&＃61;j而此处l[j]只能等于j}for(int j&＃61;m;j>&＃61;1;--j){if(a[i][j]&＃61;&＃61;a[i][j&＃43;1])r[j]&＃61;min(r[j],ra-1);else r[j]&＃61;j,ra&＃61;j&＃43;1;//同理ans&＃61;max(ans,1ll*h[j]*(r[j]-l[j]&＃43;1)*a[i][j]);}}printf("%lld\n",ans);}return 0;
}