基于线的枚举 基于块的枚举 把小矩形截出来 三角形一定是直角三角形 在三个方向上各挑一条线 小矩形内部没有横线 判断三角形 三角形是否出界 是1 15 三角形是否为空 课堂讨论 ◆三、枚举的顺序和策略 ☆☆☆☆ httpllacmpku.edu.cn/judgeonline/problemid=2172 阵中选出满足下列条件的方型区域 符合限制条件的面积最大的矩阵 #2 最高点和最低点的高度差不超过给定常数c 2:22:: 宽度不超过100 1156算法思想 ◆输入U,VC, 枚举+剪枝 宽为U,高为Ⅴ的矩阵 1、先枚举左边界 l<U<700,1<<700 2、再枚举右边界 求其于矩阵并使这个子矩阵上的海拔最大值 与最小值的差小于等于给定值C 3、对于每个左右边界构成的区间,分别 .0sCs10 求其最大矩形 矩阵元 ◆4、完成搜索后返回矩形面积最大值 ·整数Hy是xy)点的海拔高度 30000 sHy s30,0009 基于线的枚举 Š 三角形一定是直角三角形 „ 在三个方向上各挑一条线 Š 判断三角形 „ 三角形是否出界 „ 是否被横线割 „ 是否被竖线割 „ 是否被斜线切 „ 三角形是否为空 基于块的枚举 Š 把小矩形截出来 Š 小矩形内部没有横线 和竖线 课堂讨论 Š 三、枚举的顺序和策略 http://acm.pku.edu.cn/JudgeOnline/problem?id=2179 Š 从矩阵中选出满足下列条件的方型区域 „ 符合限制条件的面积最大的矩阵 „ 最高点和最低点的高度差不超过给定常数c „ 宽度不超过100 Š 输入U,V,C， „ 宽为U，高为V的矩阵 z 1 <= U <= 700, 1 <= V <= 700 „ 求其子矩阵,并使这个子矩阵上的海拔最大值 与最小值的差小于等于给定值C z 0 ≤ C ≤ 10 „ 矩阵元素 z 整数Hxy 是(x, y)点的海拔高度 z -30,000 ≤ Hxy ≤ 30,000 1156算法思想 枚举 + 剪枝: Š 1、先枚举左边界 Š 2、再枚举右边界 Š 3、对于每个左右边界构成的区间，分别 求其最大矩形 Š 4、完成搜索后返回矩形面积最大值