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;
}

  

最新文章

  1. 简单的Viewing Frustum Culling
  2. 我看见的第一个XCODE编译错误 - Command /applications.../clang failed with exit code 1
  3. java多线程系类:基础篇:04synchronized关键字
  4. 攻城狮在路上(肆)How tomcat works(三) 连接器:Connector
  5. Mac 实用工具bash-comletion介绍安装
  6. DedeCMS生成首页html静态文件的教程
  7. JavaScript学习记录总结(七)——dom对象应用之用户简单管理
  8. svn: Can&#39;t convert string from &#39;UTF-8&#39; to native encoding 的解决办法
  9. 获取文件属性信息之stat、fstat和lstat
  10. 艰苦的RAW格式数据恢复之旅
  11. c++ new delete 常踩的坑
  12. ionic新入坑-环境搭建+新建项目+打开低版本项目处理
  13. Python小代码_7_字符串的字符次数统计
  14. Python 中关于 round 函数的坑
  15. 什么是Tensor
  16. __x__(36)0908第五天__背景 background
  17. table表格固定前几列,其余的滚动
  18. IntelliJ IDEA maven springmvc+shiro简单项目
  19. 为什么我们做分布式要使用Redis
  20. el表达式不显示值

热门文章

  1. win7开防火墙,允许ping通
  2. Excel_replace
  3. 适合于图像处理方向的SCI期刊杂志列表【转】
  4. Robot Framework--11 RF结合Jenkins
  5. IdentityDbContext
  6. PHP数组处理函数的使用array_push(一)
  7. WCF-复合类型使用;传输图片
  8. JVM执行引擎总结(读《深入理解JVM》) 早期编译优化 DCE for java
  9. mysql 总结二(自定义存储过程)
  10. python文件I/O(转)