首页 > 代码库 > Vijos 1055 奶牛浴场
Vijos 1055 奶牛浴场
Description
求一个不覆盖指定点的最大子矩阵,\(n,m \leqslant 3\times 10^5,S \leqslant 5\times 10^3\) .
Sol
没有名字的算法都叫xjblg算法?
枚举每个点成为极大子矩阵边界的情况,然后维护上下边界.
还有一种情况就是左右边界是矩阵两边的情况,需要预处理一下.
时间复杂度 \(O(S^2)\) 空间复杂度 \(O(S)\)
Code
#include<cstdio>#include<utility>#include<algorithm>#include<functional>#include<iostream>using namespace std;#define mpr make_pairtypedef pair< int,int > pr;typedef long long LL;const int N = 5005;int n,m,k;LL ans;pr g[N];int x[N],y[N];inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }int main(){ n=in(),m=in(),k=in(); for(int i=1,u,v;i<=k;i++) u=in(),v=in(),g[i]=mpr(u,v),y[i]=v; g[++k]=mpr(0,0),y[k]=0,g[++k]=mpr(0,m),y[k]=m,g[++k]=mpr(n,0),y[k]=0,g[++k]=mpr(n,m),y[k]=m; sort(y+1,y+k+1); for(int l=1,r;l<=k;l=r+1){ r=l; while(r<k && y[l]==y[r+1]) ++r; ans=max(ans,(LL)m*(y[l]-y[l-1])); } sort(g+1,g+k+1,less<pr>()); for(int i=1;i<=k;i++){ int u=0,d=n; for(int j=i+1;j<=k;j++){ ans=max(ans,(LL)(g[j].first-g[i].first)*(d-u)); if(g[j].second>g[i].second) d=min(d,g[j].second); else if(g[j].second<g[i].second) u=max(u,g[j].second); else break; } } sort(g+1,g+k+1,greater<pr>()); for(int i=1;i<=k;i++){ int u=0,d=n; for(int j=i+1;j<=k;j++){ ans=max(ans,(LL)(g[i].first-g[j].first)*(d-u)); if(g[j].second>g[i].second) d=min(d,g[j].second); else if(g[j].second<g[i].second) u=max(u,g[j].second); else break; } }cout<<ans<<endl; return 0;}
Vijos 1055 奶牛浴场
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。