首页 > 代码库 > BZOJ 1057: [ZJOI2007]棋盘制作
BZOJ 1057: [ZJOI2007]棋盘制作
Decsription
给你一个矩阵,求最大了 01相间 的矩阵.
Sol
DP+悬线法.
这是一个论文啊 《浅谈用极大化思想解决最大子矩形问题》--王知昆.
枚举每一根悬线,记录最左/右/上能到达的点,统计答案.
Code
/************************************************************** Problem: 1057 User: BeiYu Language: C++ Result: Accepted Time:1384 ms Memory:95508 kb****************************************************************/ #include<cstdio>#include<cstring>#include<iostream>using namespace std; #define sqr(x) ((x)*(x))const int N = 2005; int n,m,ans1,ans2;int a[N][N],f[N][N],pre[N][N],nxt[N][N],L[N][N],R[N][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; }void work(){ memset(nxt,0,sizeof(nxt)),memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++){ pre[i][1]=1,nxt[i][m]=m; for(int j=2;j<=m;j++){ if(a[i][j]^a[i][j-1]) pre[i][j]=pre[i][j-1]; else pre[i][j]=j; }for(int j=m-1;j;--j){ if(a[i][j]^a[i][j+1]) nxt[i][j]=nxt[i][j+1]; else nxt[i][j]=j; } } for(int j=1;j<=m;j++) f[1][j]=1,L[1][j]=pre[1][j],R[1][j]=nxt[1][j],ans1=max(ans1,(R[1][j]-L[1][j]+2)),ans2=max(ans2,1); for(int i=2;i<=n;i++) for(int j=1;j<=m;j++){ if(a[i][j]^a[i-1][j]){ f[i][j]=f[i-1][j]+1; L[i][j]=max(pre[i][j],L[i-1][j]); R[i][j]=min(nxt[i][j],R[i-1][j]); }else{ f[i][j]=1; L[i][j]=pre[i][j]; R[i][j]=nxt[i][j]; } ans1=max(ans1,f[i][j]*(R[i][j]-L[i][j]+1)); ans2=max(ans2,sqr(min(f[i][j],R[i][j]-L[i][j]+1))); }// for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("%d%c",pre[i][j]," \n"[j==m]);// for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("%d%c",nxt[i][j]," \n"[j==m]);}int main(){ n=in(),m=in(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=in(); work(); cout<<ans2<<endl<<ans1<<endl; return 0;}
BZOJ 1057: [ZJOI2007]棋盘制作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。