关键词：
虽然还是悬线法，但是这道题可不能轻易地套模板了，而是要换一种思路，横着扫一遍，竖着扫一遍，时间复杂度依旧是O(n^2),然而空间复杂度有一定的优化
如果用原来的方法，显然时间空间都会炸（如果你想用map我也没办法...时间换空间？）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #define st short int using namespace std; inline int read() char chr=getchar(); int f=1,ans=0; while(!isdigit(chr)) if(chr==‘-‘) f=-1;chr=getchar(); while(isdigit(chr)) ans=(ans<<3)+(ans<<1);ans+=chr-‘0‘;chr=getchar(); return ans*f; void write(int x) if(x<0) putchar(‘-‘),x=-x; if(x>9) write(x/10); putchar(x%10+‘0‘); struct Pint x,y;a[5005]; int L,W,n,x,y,ans; bool cmp1(const P &x,const P &y)return x.x<y.x||x.x==y.x&&x.y<y.y; bool cmp2(const P &x,const P &y)return x.y<y.y||x.y==y.y&&x.x<y.x; int main() L=read(),W=read(),n=read(); for(int i=1;i<=n;i++)x=read(),y=read(),a[i]=(P)x,y; a[++n]=(P)0,0,a[++n]=(P)0,W,a[++n]=(P)L,0,a[++n]=(P)L,W; sort(a+1,a+n+1,cmp1); for(int i=1;i<=n;i++) int le=0,ri=W,cnt=i; while(a[i].x==a[cnt].x) cnt++; int j=cnt; while(j<=n) ans=max(ans,(a[j].x-a[i].x)*(ri-le)); if(a[j].y<=a[i].y) le=max(le,a[j].y); else ri=min(ri,a[j].y); ++j; le=0,ri=W,j=cnt; while(j<=n) ans=max(ans,(a[j].x-a[i].x)*(ri-le)); if(a[j].y<a[i].y) le=max(le,a[j].y); else ri=min(ri,a[j].y); ++j; sort(a+1,a+n+1,cmp2); for(int i=1;i<=n;i++) int le=0,ri=L,cnt=i; while(a[i].y==a[cnt].y) cnt++; int j=cnt; while(j<=n) ans=max(ans,(a[j].y-a[i].y)*(ri-le)); if(a[j].x<=a[i].x) le=max(le,a[j].x); else ri=min(ri,a[j].x); ++j; le=0,ri=L,j=cnt; while(j<=n) ans=max(ans,(a[j].y-a[i].y)*(ri-le)); if(a[j].x<a[i].x) le=max(le,a[j].x); else ri=min(ri,a[j].x); ++j; cout<<ans; return 0;
悬线法dp
悬线法dp出处：【转】【最大子矩阵问题】【悬线法】学习笔记注：已经有大佬的发了详解，搬过来方便以后复习学习材料：王知昆《浅谈用极大化思想解决最大子矩阵问题》【最大子矩阵问题】在一个给定的矩... 查看详情
p1578奶牛浴场(代码片段)
题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显... 查看详情
悬线法(代码片段)
...阵上的每一个点，我们可以： 1.从它向上引一条悬线，遇到边界或障碍点停止，h[i][j]数组记录从点(i,j)向上的悬线长度。 2.向左延伸，遇到边界或障碍 查看详情
动态规划悬线法(代码片段)
悬线法是用来处理子矩阵相关的问题，在一个矩形中寻找一个最大的满足条件的矩阵悬线法的基本思路，维护三个数组，l[N][N],r[N][N],up[N][N]。l[N][N]:用来记录在当前这个位置满足条件的左边界，也就是可以往左延... 查看详情
悬线法刷题记录(代码片段)
最近学习了悬线法，用极大化思想解决最大子矩阵问题，一种dp问题，留个记录……讲的特别好的一个博客：极大化思想解决最大子矩阵问题例题： P1169[ZJOI2007]棋盘制作代码如下：1#include<iostream>2#include<cstdio>... 查看详情
bzoj3039玉蟾宫悬线法(代码片段)
悬线法是一种更优秀的枚举方式，保证了枚举悬线的集合包含了极大子矩形所在的集合，而且由最大子矩形一定是极大子矩形的定理可知，这种枚举方式可以求出最大子矩形。具体做法是维护矩形中每个元素对应最近的左边和右... 查看详情
洛谷1578：[wc2002]奶牛浴场——题解(代码片段)
...gu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置... 查看详情
[luogup1578]奶牛浴场（dp）
传送门 O(s2)算法详见论文 王知昆--浅谈用极大化思想解决最大子矩形问题我就复制你能把我怎么样QAQ#include<cstdio>#include<iostream>#include<algorithm>#defineN5010#definemax(x,y)((x)>(y)?(x):(y))#definemin(x,y)((x)& 查看详情
动态规划之悬线法模板（最大子矩阵问题）(代码片段)
悬线法的用途针对求给定矩阵中满足某条件的极大矩阵，比如“面积最大的长方形、正方形”“周长最长的矩形等等”。可以满足在时间复杂度为O（M*N）的要求，比一般的枚举高效的多，也易于理解。悬线法... 查看详情
2019年acm银川站h题_悬线法(代码片段)
...出这个子矩阵中的元素个数。所以输出4。思路：采用悬线法悬线法用来求直方图中最大矩形的面积。在直方图的每个柱体顶端悬挂一根线，然后将线左右移动，并分别记录该移动的最左端和最右端。左右两端的长度... 查看详情
hdu4328cutthecake（动规：最大子矩形问题/悬线法）(代码片段)
题目链接：传送门题目大意： 给出N*M的字符矩阵（由字符B/R组成），求符合下图条件的子矩阵的最大周长。 1≤N，M≤1000。 &n... 查看详情
[zjoi2007]棋盘制作（悬线法）(代码片段)
题目描述国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8 imes88×8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主... 查看详情
最大子矩阵扫描法和悬线法(代码片段)
博客主页:https://blog.csdn.net/qq_50285142欢迎点赞👍收藏✨关注❤留言📝如有错误，敬请指正🎈虽然生活很难，但我们也要一直走下去🎈最大子矩阵问题在一个给定的n∗mn*mn∗m矩形网格中有nnn个障碍点，... 查看详情
zjoi2007棋盘制作-悬线法(代码片段)
...全国信息学竞赛的你，你能帮助他么？思路本题用到的是悬线法悬线法的用途:解决给定矩阵中满足条件的最大子矩阵需要用到这几个东西left[i][j]:代表从(i,j)能到达的最左位置right[i][j]:代表从(i,j)能到达的最右位置up[i][j]:代表从(i... 查看详情
[codevs1159]最大全0子矩阵(悬线法)(代码片段)
解题关键：悬线法模板题。注意此模板用到了滚动数组。#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<iostream>#include<cmath>#definemaxn2002usingnamespacestd;typedeflonglongll;intmap[maxn][maxn],l[maxn],r[maxn],h... 查看详情
动态规划之悬线法(代码片段)
例题：[ZJOI2007]棋盘制作先贴代码：#include<cstdio>#include<algorithm>usingnamespacestd;#defineFor(i,a,b)for(inti=(a);i<=(b);i++)#defineFord(i,a,b)for(inti=(a);i>=(b);i--)constintmaxn=2005;intn,m,a[maxn][maxn],MaxS,MaxJ,lef[maxn][maxn],rig[maxn][maxn],up[maxn][maxn];intm... 查看详情
p1578奶牛浴场
P1578奶牛浴场 题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位... 查看详情
洛谷p1578奶牛浴场
P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情