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