重庆黄页网站,网站设计职业培训,网站建设步骤流程详细介绍,网站建设基本问题最大子矩阵#xff08; $ s^2 $ 枚举障碍与 $ n \times m $ 悬线法#xff09; 题目大意#xff1a; 有 $ s $ 个障碍分布在一个 $ n\times m $ 的矩阵中。现在让你找出其中不包含任何一个障碍的最大子矩阵。 首先我们要引进一个新概念#xff1a;#xff08;极大子矩阵 $ s^2 $ 枚举障碍与 $ n \times m $ 悬线法 题目大意 有 $ s $ 个障碍分布在一个 $ n\times m $ 的矩阵中。现在让你找出其中不包含任何一个障碍的最大子矩阵。 首先我们要引进一个新概念极大子矩阵所有边都不能再向外扩张的合法矩阵 极大化思想最大子矩阵一定是一个极大子矩阵 $ solution~1:~O(s^2) $ 首先讲一个 $ O(s^5) $ 算法枚举两个对角端点就是四个边界然后枚举障碍判断这个矩阵是否合法。这个算法很不优因为它枚举了很多不是极大子矩阵的矩阵就是个纯暴力。 所以我们优化一下 $ O(s^3) $ 枚举左右边界然后将边界内的点按y轴排序每两个相邻的点和左右边界组成一个合法矩阵。这个算法也枚举了左右边界会产生非极大子矩阵的矩阵。 所以我们需要找到一种枚举方案使得矩阵合法极大子矩阵两个条件尽量满足于是 为了不做多余运算我们以点为边界 $ O(s^2) $ 将点按照横坐标排序依次枚举每一个点作为矩阵的左边界只要左边界再向左移就会碰到这个点然后我们枚举它右边的点作为右边界并在枚举同时更新上下边界。因为一个合法的矩阵不能有障碍所以枚举的这些点会限制上下边界上下边界以外的矩阵不用考虑因为他们的左边界不是当前的最外层枚举的那个点所限制的也就是说它们的左边界不是当前枚举的左边界。不过要注意我们的 $ n \times m $ 的大边界也可作为极大子矩阵的边界所以还需要倒着来一遍。 例题$ POJ~3197~Corral~the~Cows $ 二分最大子矩阵 这道题并不是一道正宗的最大子矩阵但是它同样用到了枚举点的思想博主刷题不多先用着凑活一下大家只需要知道这种方法就行。 $ Code: $ #includeiostream
#includecstdio
#includeiomanip
#includealgorithm
#includecstring
#includecstdlib
#includectime
#includecmath
#includevector
#includequeue
#includemap
#includeset#define ll long long
#define db double
#define rg register intusing namespace std;int n,c;struct su{int x,y;inline bool operator (const su z)const{return yz.y;}
}a[505];inline bool cmp (const su x,const su y){if(x.xy.x)return x.yy.y;return x.xy.x;
}inline int qr(){register char ch; register bool sign0; rg res0;while(!isdigit(chgetchar()))if(ch-)sign1;while(isdigit(ch))resres*10(ch^48),chgetchar();if(sign)return -res; else return res;
}inline bool check(int x){multisetsu s; rg res0;for(rg i1,j1;in;i){while(jna[i].xx-1a[j].x)s.insert(a[j]), j;multisetsu::iterator l,r;lrs.begin(); res0;while(l!s.end()){while(r!s.end()(*r).y-(*l).y1x) r,res;l; if(resc)return 0; --res;}s.erase(s.find(a[i]));}return 1;
}int main(){//freopen(.in,r,stdin);//freopen(.out,w,stdout);cqr(); nqr();for(rg i1;in;i)a[i].xqr(),a[i].yqr();sort(a1,an1,cmp);rg l1,r10000,mid;while(lr){mid(lr)1;if(check(mid))lmid1;else rmid-1;}printf(%d\n,l);return 0;
}$ solution~2:~O(n\times m) $ 悬线法 这是很早之前学的东西了就当做个总结 上文我们已经提到了极大子矩阵还有一个 $ s^2 $ 做法但是这个做法在障碍比较多的时候是不行的。所以我们考虑另一种与边界长度有关的最大子矩阵做法。上一种做法里我们强调让枚举的矩阵尽量是极大子矩阵这个思想在悬线法中也是核心地位。 我们知道每一个点向上向左向右的合法极大子矩阵有很多个注意没有向下。所以我们不可能将每个点的向上向左向右的合法极大子矩阵求出来这样会有大量重复。所以我们钦定从每一个点向上碰到的第一个障碍为上边界然后向左右尽量延伸所得到的矩阵为这个点用悬线法得到的矩阵之所以不向下是为了方便从第一排开始递推寻找这个矩阵。我们可以从这个矩阵的定义里知道所有极大子矩阵一定都可以用这种方式被找出来证明极大子矩阵的上边界的上一排一定有一个障碍这个障碍一直向下到这个极大子矩阵的下边界所对应的那个点它用悬线法求出的矩阵就是这个极大子矩阵。而最大子矩阵被包含在极大子矩阵中所以悬线法的正确性得到证明。接下来是复杂度和过程详解。 我们需要求出每一个点用悬线法求得的矩阵。为此我们先求出每个点向左端延伸的最远距离向右端延伸的最远距离向上延伸的最远距离。然后开始枚举整个 $ n \times m $ 的矩阵过程是从第一排向下递推。因为我们求的是一个矩阵所以当前点在这一排向左向右延伸的最远距离不是所求矩阵的最远距离它还受到上面几排的左右端的影响所以我们从第一排向下推。然后我们这个点用悬线法得到的矩阵的最左端就是它在当前排向左的最远距离和上面那些点到最左端的距离的最小值这个递推记录一下就好右端点同理而矩阵的高从一开始就确定了然后直接计算就好 注意每个点向左端延伸的最远距离向右端延伸的最远距离可以边悬线法边求。 例题洛谷 $ P4147 $ 玉蟾宫 $ Code: $ #includebits/stdc.h
using namespace std;
int n,m,i,j,l[1001][1001],r[1001][1001],h[1001][1001],tot;
int main(){char c;scanf(%d%d,n,m);for(i1;in;i)for(j1;jm;j){cinc;if(cF)h[i][j]h[i-1][j]1;}for(i1;im;i)r[0][i]m1;for(i1;in;i){int f0;for(j1;jm;j){if(h[i][j])l[i][j]max(l[i-1][j],f);else fj;}fm1;for(jm;j1;j--){if(h[i][j])r[i][j]min(r[i-1][j],f);else r[i][j]m1,fj;}for(j1;jm;j)totmax(tot,(r[i][j]-l[i][j]-1)*h[i][j]);}couttot*3;return 0;
} 转载于:https://www.cnblogs.com/812-xiao-wen/p/11251533.html
