2016-05-31 14:56:17

题目链接: 洛谷 P1169 [ZJOI2007]棋盘制作

题目大意:

  给定一块矩形,求出满足棋盘式黑白间隔的最大矩形大小和最大正方形大小

解法:

  神犇王知昆的悬线法

  论文:浅谈用极大化思想解决最大子矩形问题

  H[i][j]表示(i,j)向上最长连续多少距离不出现障碍点(悬线)

  L[i][j]表示H[i][j]这根悬线最多可以向左移到什么位置

  R[i][j]表示H[i][j]这根悬线最多可以向右移到什么位置

  递推方式看代码吧,很好理解的

 //棋盘制作 (ZJOI2007)
//悬线法 矩形DP
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=;
int H[maxn][maxn];
int L[maxn][maxn];
int R[maxn][maxn];
bool map[maxn][maxn];
int N,M;
int ans1;
int ans2;
int main()
{
scanf("%d %d",&N,&M);
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
int x;
scanf("%d",&x);
map[i][j]=x;
if(i==)H[i][j]=;
else if(map[i][j]!=map[i-][j])H[i][j]=H[i-][j]+;
else H[i][j]=;
}
}
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
L[i][j]=j;
while(L[i][j]>&&map[i][L[i][j]-]!=map[i][L[i][j]]&&H[i][L[i][j]-]>=H[i][j])
{
L[i][j]=L[i][L[i][j]-];
}
}
for(int j=M;j>=;j--)
{
R[i][j]=j;
while(R[i][j]<M&&map[i][R[i][j]+]!=map[i][R[i][j]]&&H[i][R[i][j]+]>=H[i][j])
{
R[i][j]=R[i][R[i][j]+];
}
}
for(int j=;j<=M;j++)
{
int dx=R[i][j]-L[i][j]+;
int dy=H[i][j];
ans1=max(ans1,dx*dy);
ans2=max(ans2,min(dx,dy)*min(dx,dy));
}
}
printf("%d\n%d",ans2,ans1);
}

最新文章

  1. 一文搞懂HMM(隐马尔可夫模型)
  2. JAVA内存管理
  3. 20145330第六周《Java学习笔记》
  4. 深入了解Ant构建工具 命令
  5. Get code int value for different encoding
  6. EffectiveC#2--为你的常量选择readonly而不是const
  7. C# Socket 简易的图片传输
  8. 【数学】HPU--1037 一个简单的数学题
  9. SpringMvc Ant通配符的使用
  10. shell脚本实现并发控制
  11. Axure PR的使用
  12. React 记录(7)
  13. [再寄小读者之数学篇](2014-06-23 积分不等式 [中国科学技术大学2013年高等数学B 考研试题])
  14. h3c mstp的举例
  15. 服务网关zuul之四:zuul网关配置
  16. GoLang学习之变量定义和初始化
  17. springBoot的搭建使用记录
  18. mysql hive sql 进阶
  19. view_countInfo
  20. Maven解读:项目依赖管理如何优化

热门文章

  1. Linux命令ln的使用
  2. JSP中脚本、声明和表达式的本质区别
  3. 深入浅出 ES6:ES6 与 Babel / Broccoli 的联用
  4. 函数可重入问题reentrant functions(函数执行过程中可以被中断,允许多个副本)
  5. WPF之给使用了模板的MenuItem添加快捷操作
  6. Android 监听EditView中的文本改变事件
  7. nginx负载均衡 - session失效
  8. vmware-tools安装指南
  9. Java之iterator迭代器和iterable接口
  10. Java面试题-多线程