首页 > 代码库 > BZOJ 3736: [Pa2013]Karty
BZOJ 3736: [Pa2013]Karty
Description
一个0/1矩阵,求能覆盖所有 \(1\) ,同时不覆盖所有 \(0\) 的矩阵,使这个面积最大.
Sol
DP/悬线法.
首先,所求的矩阵一定可以覆盖所有贴边的悬线.
用悬线法求出,高度为 \(r\) 最大的 \(c\) ,宽度为 \(c\) 最大的高度.
上下左右都要做一遍,然后更新统计答案.
上下的时候统计的是每一个高度,左右的时候统计的是每一个宽度.
这样就可以保证所有矩阵都是一个合法的矩阵了.
我多开了几个数组,发现空间炸了...然后我就开始滚了...
Code
/************************************************************** Problem: 3736 User: BeiYu Language: C++ Result: Accepted Time:6888 ms Memory:50412 kb****************************************************************/ #include<cstdio>#include<cstring>#include<iostream>using namespace std; #define clr(a) memset(a,0,sizeof(a))#define debug(a) cout<<#a<<"="<<a<<" "const int N = 2505; int n,m,ml,mw,s;int a[N][N],tmp[N][N],f[2][N],L[2][N],R[2][N],l[N],r[N];int mxc[N],mxr[N]; void work(int mxc[]){ for(int j=1;j<=m;j++) L[0][j]=0,R[0][j]=m+1,f[0][j]=0; for(int i=1,cur=1;i<=n;i++){ l[0]=0,r[m+1]=m+1; for(int j=m;j;--j) if(a[i][j]) r[j]=r[j+1];else r[j]=j; for(int j=1;j<=m;j++) if(a[i][j]){ l[j]=l[j-1],f[cur][j]=f[cur^1][j]+1,L[cur][j]=max(L[cur^1][j],l[j]),R[cur][j]=min(R[cur^1][j],r[j]); int r=f[cur][j],c=R[cur][j]-L[cur][j]-1; mxc[r]=min(mxc[r],c);if(!a[i+1][j]){ for(int p=r+1;p<=n;p++) if(mxc[p]) mxc[p]=0;else break; } }else l[j]=j,f[cur][j]=0,L[cur][j]=0,R[cur][j]=m+1; cur^=1; }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ char ch=getchar();while(ch!=‘_‘ && ch!=‘X‘) ch=getchar(); for(int j=1;j<=m;j++) a[i][j]=ch==‘X‘,ch=getchar(); } ml=mw=N,s=0;memset(mxc,0x3f,sizeof(mxc)),memset(mxr,0x3f,sizeof(mxr)); work(mxc); for(int j=1;j<=m;j++) for(int i=1;i<=n/2;i++) swap(a[i][j],a[n-i+1][j]); work(mxc); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) tmp[j][i]=a[i][j],a[i][j]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) a[i][j]=tmp[i][j]; swap(n,m); work(mxr); for(int j=1;j<=m;j++) for(int i=1;i<=n/2;i++) swap(a[i][j],a[n-i+1][j]); work(mxr); swap(n,m); mxr[0]=n+1; for(int i=n,j=1;j<=m;j++) for(;i>mxr[j];--i) mxc[i]=min(mxc[i],j-1); for(int i=1;i<=n;i++) if(i*mxc[i]>s) s=i*mxc[i],ml=i,mw=mxc[i]; printf("%d %d\n",ml,mw); return 0;}
BZOJ 3736: [Pa2013]Karty
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。