枚举法 主要内容 ◆1、枚举法思想简介 基本算法介绍之 ◆2、利用枚举法解题 2,1百钱百鸡☆ 张铭 22猴子分桃☆ 2007.9.19 23宴会彩灯☆ 24质数方阵☆☆ 3、枚举s,搜索 1、枚举法思想简介 引子 ◆基本思想 填写运算符 枚举也称穷举,指的是从问题可能的解的集 合中一 输入任意5个数xI、x2、x3、 枚举各元童 两个数间填上一个运算 用题目给定的检验条件判定哪些是无用的 个运算符后,使得表达 哪些是有用的。能使命题成立,即为其解。 y(y由健盘输入)。求出 结录升析 ◆典型应用举例:密码破艉 枚举次数 ·要执行4=256次,当数字的个数超过207 最坏情况kn 枚举法初体验 2、利用枚举法解题 少<~·枚举法的特点是算法简单,但是运算量 ◆优化策略 大是它的缺点。当问题的规模变大,循 减少枚举次数 环的阶数愈大,执行的速度愈慢。 ·合理选择用于枚举的变量 注意枚举的顺序 从全局观点使用枚举法,计算量容 减少判断每种情况的时间 易过大。在局部地方使用枚举法 其效果会十分显著
1 枚举法 —— 基本算法介绍之一 张铭 2007.9.19 主要内容 1、枚举法思想简介 2、利用枚举法解题 2.1 百钱百鸡 2.2 猴子分桃 2.3 宴会彩灯 2.4 质数方阵 3、枚举 vs. 搜索 1、枚举法思想简介 基本思想 枚举也称穷举，指的是从问题可能的解的集 合中一一枚举各元素。 用题目给定的检验条件判定哪些是无用的， 哪些是有用的。能使命题成立，即为其解。 典型应用举例： 密码破解： 枚举次数： 最好情况1 最坏情况 n k 密码破解 引子 填写运算符 输入任意5个数 x1、x2、x3、x4、x5. 每 相邻两个数间填上一个运算符。在填人四 个运算符后，使得表达式值为一个指定值 y(y由键盘输入)。求出所有满足条件的表达 式。 结果分析 要执行 ＝256次。当数字的个数超过20？ 4 4 枚举法初体验 枚举法的特点是算法简单，但是运算量 大是它的缺点。当问题的规模变大，循 环的阶数愈大，执行的速度愈慢。 从全局观点使用枚举法，计算量容 易过大。在局部地方使用枚举法， 其效果会十分显著。 2、利用枚举法解题 优化策略 减少枚举次数 z 合理选择用于枚举的变量 z 注意枚举的顺序 减少判断每种情况的时间
21百钱买百鸡☆ 最简单直接的做法 ◆鸡翁一,值钱五,鸡母一,值钱三,鸡 ◆根据方程写程序 值4 (X=0;x<100;x++) 枚举次数: 百钱买百鸡,问鸡翁 母、雏各几何? for(y-0;y<100-xy+)I=55次 ◆根据题意列方程 Z100-X-y f(%3=0 5X+3y+z/3= &&15*x+9y+z=30) y+z=10 另解 枚举次数大大减少 ◆根据整理后的方程写程序 5X+3y+z/3=100 观察方 ·for(x0;x<14:;x++ xy,z≥=03除z 枚举次数 v·100-7*x; X+4y=100 if (z %3)continue; x+y+z=100 v<<<<z<<endl 22猴子分桃子☆ 有一堆桃子和甲乙两组猴子,甲组3只猴子,乙组5 ◆第8只猴子来过后,还剩R8个桃子 组猴子先看到桃子 只猴子把桃子均分 第7只来过后,还剩R7个桃子 走了。第二、第三只猴子亦照样办理。 ◆第8只猴子拿走了一堆,还吃了一个 到了桃 这 R8/(5-1)=R8/4是它原来按5份分时的总量 还要加1,才是它看到的原始量 堆便走了。第二、第三、第四、第五只猴子亦照 样办理 R7=R8/4*5+1 请问:8只猴子分别来过之后,至少还剩多少个桃 ◆其他依次类推 子?原来至少有多少个桃子
2 2.1 百钱买百鸡 根据题意列方程： 鸡翁一，值钱五，鸡母一，值钱三，鸡 雏三，值钱一。百钱买百鸡，问鸡翁、 母、雏各几何？ 5x + 3y + z/3 = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) 最简单直接的做法 for (x = 0; x = 0; 3整除z) 7x + 4y = 100 x + y + z = 100 (x, y, z >= 0; 3整除z) 观察方程的 特点，消去 一个未知数z 枚举次数大大减少 for (x = 0; x <= 14; x++) { y = 100 - 7 * x; if (y % 4) continue; else y /= 4; z = 100 - x - y; if (z % 3) continue; cout<<x<<' '<<y<<' '<<z<<endl; } 根据整理后的方程写程序： 枚举次数： 5151 VS 14 2.2 猴子分桃子 有一堆桃子和甲乙两组猴子，甲组3 只猴子，乙组5 只。 甲组猴子先看到桃子，第一只猴子把桃子均分成3 堆，结果剩下2 个，它吃了这两个，又拿了一堆便 走了。第二、第三只猴子亦照样办理。 甲组走后，乙组又看到了桃子，第一只猴子把桃子 均分成5 堆，结果剩下1 个，它吃了这一个，又拿了 一堆便走了。第二、第三、第四、第五只猴子亦照 样办理。 请问：8 只猴子分别来过之后，至少还剩多少个桃 子？原来至少有多少个桃子？ 第8只猴子来过后，还剩R8个桃子 第7只来过后，还剩R7个桃子…… 第8只猴子拿走了一堆，还吃了一个 R8/(5-1)=R8/4是它原来按5份分时的总量 z 还要加1，才是它看到的原始量 R7 = R8 / 4 * 5 + 1 其他依次类推
选择适当的枚举量 92.3质数方阵 递推关系式 右下图表示了一个方阵,沿 R0=RI/2*3+2 行、沿列及两个对角线的5个11351 ◆RI=R2 数字均组成一个5位的质数 33203 R2=R3/2*3+2 拥蕉互貧 对于行,自左向右读数;对于30323 R3=R4/4*5+1 列,自上向下读数;对于对角 R4=R5/4*5+1 线,两个对角线均自左向右读 33311 R5=R6/4*5+ 数 R6=R7/4*5+1 R7=R8/4*5+1 质数方阵 所有位置的可能取值情况 ◆现在给定两个数和A,编程 个确定矩阵中 按以下要求构成方阵 不能是11351 每个元素: 零,例如0000是位质数 33203 最左一列、最上一行元9101010 每个质数的各位之和均为s(右30323 14033 根据质数的限制,最右 ·方阵左上角中的数字为A(右图33311 不能是 数,也不能是5 个5位质数在同一方阵中可以 则每个位量的可能取值 被使用多次 的情况如右图 若存在多个解,必须全部给出 策略:选择适当的枚举顺序 质数的判断 ◆减少枚举次数 质数的判断:如何提高判断的效率? ·某些元囊可以由已知元素直 接确定〔和为S) ·方法1;sqrt(100000=316,小于316 适当选择每个元章确定的顺 的质数有65个,事先记录在数组中。 序,可以减少枚举次数 如果这个五位数不能被这65个质微中 的任何一个整除则必为质数 ·顺序确定原则:尽量由已知 元素确定未知元囊 方法2:事先求出所有和为s的所有五位 右图是一种枚举顺 进套教::6次质数判断用二分法
3 选择适当的枚举量 R0 = R1 / 2 * 3 + 2 R1 = R2 / 2 * 3 + 2 R2 = R3 / 2 * 3 + 2 R3 = R4 / 4 * 5 + 1 R4 = R5 / 4 * 5 + 1 R5 = R6 / 4 * 5 + 1 R6 = R7 / 4 * 5 + 1 R7 = R8 / 4 * 5 + 1 递推关系式： R0> R1> …R7>R8 是一组相互依赖 的解向量，只需 枚举其中的一 个，应该选择哪 个量进行枚举？ 2.3 质数方阵 右下图表示了一个方阵，沿 行、沿列及两个对角线的5个 数字均组成一个5位的质数。 对于行，自左向右读数；对于 列，自上向下读数；对于对角 线，两个对角线均自左向右读 数。 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 质数方阵 现在给定两个数S和A，编程 按以下要求构成方阵。 5位质数中的第一个数字不能是 零，例如00003不是5位质数。 每个质数的各位之和均为S（右 图中S = 11）。 方阵左上角中的数字为A（右图 中A = 1）。 一个5位质数在同一方阵中可以 被使用多次。 若存在多个解，必须全部给出。 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 4 4 9 9 所有位置的可能取值情况 枚举逐个确定矩阵中的 每个元素： 最左一列、最上一行元 素不为0。 根据质数的限制，最右 一列、最下一行不能是 偶数，也不能是5。 则每个位置的可能取值 的情况如右图： 9 9 10 9 10 10 10 10 10 4 4 4 9 10 10 9 10 9 4 4 4 4 策略：选择适当的枚举顺序 减少枚举次数： 某些元素可以由已知元素直 接确定（和为S ）。 适当选择每个元素确定的顺 序，可以减少枚举次数。 顺序确定原则：尽量由已知 元素确定未知元素。 右图是一种枚举顺序： a b c d e f m n l o g p k r s h j t v w i q u x y 质数的判断 质数的判断：如何提高判断的效率？ 方法1：sqrt (100000) ＝ 316，小于316 的质数有65个，事先记录在数组中。 如果这个五位数不能被这65个质数中 的任何一个整除则必为质数。 方法2：事先求出所有和为S的所有五位 质数（最多757个，S = 23时取到）， 记录在数组中。每次质数判断用二分法 进行查找即可
质数方阵题小结 24宴会上的彩灯☆ ◆算法效率分析 续址是全共物#2 在的方法需要枚举多少次? 置:姦券福廷堑爹灯巯绕 关灯游戏 Turnofflight swf 质数判断的两种优化方法各最多需要几次判断? 小试牛刀 http:/acm.pku.edu.cn/judgeOnline/showproblem?problemid 彩灯状态转换示意图 观察得到的结论 ◆每个开关最多被操作一次,因为操作两次 的结果相当于没有操作。 第i的灯的状态只能由第i-1,i计+1行的开 ◆如果第i-1,i开关状态已经确定,为了要 关上第i的灯,第i+1行开关的状态也就 被唯一确定 关灯策略:局部枚举 一个例子 枚举对第一行开关的操作 ·桔色:灯亮 蓝色:灯 ·按动第二行的开关,把第一行的 ·按忸:开关 灯都关 按动第三行的开关,把第二行的 的灯关上 输出结果是 100111 按动第五行的开关,看是否可以 ll0000 恰好第四行和第五行的灯的灯 000100 Il0101 101101
4 质数方阵题小结 算法效率分析： http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=11 65 小试牛刀 减少枚举次数 减少判断每种情况的时间 现在的方法需要枚举多少次？还能不能更快？ 质数判断的两种优化方法各最多需要几次判断？ 2.4 宴会上的彩灯 在举行宴会的房间的一面墙上，30盏 彩灯排成5行6列，每盏灯带有1个开 关。按动某盏灯的开关，它和它上下 左右的灯都会转变状态。 宴会之后，这些彩灯有开有关，愁煞 了管理员。如何才能将这些彩灯统统 关上呢？ 关灯游戏 TurnoffLight.swf 开关的状态 有230种可能 彩灯状态转换示意图 观察得到的结论 每个开关最多被操作一次，因为操作两次 的结果相当于没有操作。 第i行的灯的状态只能由第i-1, i, i+1行的开 关控制。 如果第i-1, i行开关状态已经确定，为了要 关上第i行的灯，第i+1行开关的状态也就 被唯一确定。 关灯策略：局部枚举 枚举对第一行开关的操作。 按动第二行的开关，把第一行的 灯都关。 按动第三行的开关，把第二行的 的灯关上。 …… 按动第五行的开关，看是否可以 恰好第四行和第五行的灯的灯。 一个例子 桔色：灯亮 蓝色：灯灭 按钮：开关 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 输出结果是：
彩灯题小结 3、枚举vs.搜索 ◆效率比较: 枚举本质上属于搜索算法 ■行遍所有可能 合理的顺序和剪枝可以提高效率 结论: ·对阿题进行分析,你会发现需要枚举的东西 ◆枚举的适用范围 往往没有想象的那么多 1.可预先确定解的个数n 2.解变量A,A2,…,Aq的值的可能变 ◆小试牛刀 化(范围预先确定) http:/lacmpku.edu.cn/judgeonline/showproblemPRoblemide 结论 四皇后问题及其解空间树 枚举是一种非常基本的算法思想 实现简单 常用实现方法:多循环(fo循环,whil循环) 效率较低 对问题多加分析,减少循环数和次数 是否有其它更好的方法? 回测法、分支限定法是枚举法的推广 课堂讨论 枚举和字符串操作 ◆每个字母都有一个权值 http://acmpku.edu.cn/judgeOnline/showproblem?p ◆给定字母表,表中字符可以重复 roblem id=1171(Letter Game) 给定一个字典 字典的大小不超过4000 给定单词长度不超过7
5 彩灯题小结 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id= 1222 26 230 效率比较： 小试牛刀： 结论： VS 对问题进行分析，你会发现需要枚举的东西 往往没有想象的那么多。 3、枚举 vs. 搜索 枚举本质上属于搜索算法 行遍所有可能 合理的顺序和剪枝可以提高效率 枚举的适用范围 1．可预先确定解的个数n 2．解变量Al，A 2， …，Aq的值的可能变 化（范围预先确定） 结论 枚举是一种非常基本的算法思想 实现简单 z 常用实现方法：多重循环（for循环，while循环） 效率较低 z 对问题多加分析，减少循环重数和次数 z 是否有其它更好的方法？ z 回溯法、分支限定法是枚举法的推广 四皇后问题及其解空间树 1 2 4 3 5 6 7 4 3 9 8 10 11 12 2 4 4 2 3 14 13 15 16 17 2 3 3 2 4 X1=1 18 20 19 21 22 23 3 4 4 3 1 25 24 26 27 28 1 4 4 1 3 30 29 31 32 33 1 3 3 1 4 2 34 36 35 37 38 39 2 4 4 2 1 41 40 42 43 44 1 4 4 1 2 46 45 47 48 49 1 2 2 1 4 3 50 52 51 53 54 55 2 3 3 2 1 57 56 58 59 60 1 3 3 1 2 62 61 63 64 65 1 2 2 1 3 4 X2=2 X3=3 X4=4 Q Q Q Q 课堂讨论 一、枚举和字符串操作 http://acm.pku.edu.cn/JudgeOnline/showproblem?p roblem_id=1171 (Letter Game) 每个字母都有一个权值 给定字母表，表中字符可以重复 给定一个字典 字典的大小不超过40000 给定单词长度不超过7
枚举 ◆要求在字典中选择一个或者两个单词 ◆1.只有一个单词的情况,枚举所有的单 所用的所有字母都在字母表中出现 词,并且判断 每个字母出现的次数不超过字母表中规定的 ■它是否满足约束条件(字母频率限制 次数限制 其权值是否最大 每个单词的字母个数满足至少3个最多7个 ◆2.两个单词的情况 所有字母的权值之和最大 首先枚举满足约束条件的第一个单词 再枚举第二个 联合起来判断是否满足条件 剪枝 时空分析 ◆单词长度的限制 字典规模n 至少3,最多7 给定单词长度也不会超过 僧况是势的率的调个耍且要带2 这样就是 因此,两个单词的情况 条件,实际 只枚举那些长度为3和4的单词 ·存储字典,字典中单词字母的频率 问题简述 课堂讨论 个M×N的金属板,从水平方向竖直方向以及对角线方 向切割求最终切得到三角形的个数 二、枚举的方式 ☆☆☆☆☆ POJ 2179-Inlay Cutters http://acmpku.edu.cn/judgeoNline/showproblem?P roblem id=2179 6
6 要求在字典中选择一个或者两个单词 所用的所有字母都在字母表中出现 每个字母出现的次数不超过字母表中规定的 次数限制 每个单词的字母个数满足至少3 个最多7 个 所有字母的权值之和最大 枚举 1. 只有一个单词的情况，枚举所有的单 词，并且判断 它是否满足约束条件（字母频率限制） 其权值是否最大 2. 两个单词的情况 首先枚举满足约束条件的第一个单词 再枚举第二个 联合起来判断是否满足条件 剪枝 单词长度的限制 至少3 ，最多7 给定单词长度也不会超过7 因此，两个单词的情况 只枚举那些长度为3和4的单词 z 3-3 z 3-4 z 4-3 时空分析 字典规模n 时间 最坏情况是枚举所有单词，而且要枚举2次，这样就是 O(n*n)，n为总的单词的个数 加入剪枝条件，实际的运行效果会一些好。 空间 存储字典，字典中单词字母的频率 O(n) 课堂讨论 二、枚举的方式 POJ 2179 – Inlay Cutters http://acm.pku.edu.cn/JudgeOnline/showproblem?p roblem_id=2179 8 × 4 4 × 4 问题简述 一个M×N的金属板,从水平方向,竖直方向,以及对角线方 向切割.求最终切得到三角形的个数. 1 2 3 4 5 6 1 2 3 4 5 6 7 8
输入数据及输出数据 问题分析 第一行为三个整数MN(1≤MN≤50)和K(0≤K≤296) ◆这是一道数区域的个数的题 以下行,每行四个数Cx1uY,1,X12Y1,2)表示一次切 ◆三角形的个数似乎应该与交点的个数有关 输出 一个整数切割后得到的三角形的个数 0个交点 2个三角形 个交点 1个三角形 枚举算法 问题分析 ◆基于点的枚举 ◆计算出所有的多边形判断其是否为三角 流行算法 ◆基于线的枚举 ◆基于块的枚举 ◆优化 例如分治 问题分析 三角形的分类 ◆问题规模很小,0≤M,N≤50 ◆按对角线的方向来分 ◆对于计算机而言如果它能够像人一样数 三角形那解决这个问题就很容易 所以我们只要教会计算机怎么数就可以 团4令 ◆用搜索的办法枚举出所有的三角形
7 输入数据及输出数据 输入: 第一行为三个整数M,N(1≤M,N≤50)和K(0≤K≤296). 以下K行,每行四个数(Xi,1,Yi,1,Xi,2,Yi,2)表示一次切 割,(Xi,1,Yi,1)和(Xi,2,Yi,2)是金属板边缘上的两点. 输出: 一个整数,切割后得到的三角形的个数. 问题分析 这是一道数区域的个数的题. 三角形的个数似乎应该与交点的个数有关. 0个交点 2个三角形 1个交点 1个三角形 没有明显的规律 枚举算法 基于点的枚举 流行算法 基于线的枚举 基于块的枚举 优化 例如分治 问题分析 计算出所有的多边形,判断其是否为三角 形 看来很复杂 问题分析 问题规模很小,0≤M, N≤50. 对于计算机而言,如果它能够像人一样数 三角形,那解决这个问题就很容易. 所以,我们只要教会计算机怎么数就可以 了. 用搜索的办法枚举出所有的三角形 三角形的分类 按对角线的方向来分
数据结构 数据结构 ·在边框上添加四条线段 ◆使用一个M+1)N+1)*4的boo数组 即map||0-map叫N|0true,0≤I≤M Maplillil|dl-true,表示从d这个方向上有 mapo2|= mapI|2|true0≤I≤N 线经过点(i,j 8×4 数三角形的办法 数三角形的办法 分别数出每一种三角形的个数 ◆在向后寻找另外两个顶点的时候如果存 翘的户角形先个竞它封为商 在如图所示的线中的任意一条则停止 个顶点 MapLx,Ity ][1] Il (x1,y1) Map[xa][y J [2] II Map[x,][y [3] Il Map [xo] yo1[0]=true Map[xzl [y2][o] II Maplxo]Lyo][2]=true Mapx2]y2t2】 Map [x] y,][3]=true Map[x,][y:][3] II Mapx, -1]y,][3] 数三角形的办法 数三角形的办法 如果停止的时候x1y1)与(x2y2)满足条件 ◆其他三角形的做法与第一种基本相同 mapx,lly, 1[2]&& mapx,-1|[y2 /3), y 找到一个符合题意的三角形否则所寻找 的三角形不存在 (x2-1,y2)(x2,y2)
8 数据结构 使用一个(M+1)*(N+1)*4的bool数组 Map[i][j][d]=true,表示从d这个方向上有 一条线经过点(i, j). 0 1 2 3 数据结构 在边框上添加四条线段 即 map[I][0][0]=map[I][N][0]=true,(0≤I≤M) map[0][I][2]=map[M][I][2]=true,(0≤I≤N) 8 × 4 数三角形的办法 分别数出每一种三角形的个数 例如数第三种三角形:先选一个点确定其为三角 形 的左顶点,然后逐步“摸索”着确定它的另外两 个顶点. (x1,y1) (x0,y0) (x2,y2) Map[x0][y0][0]=true Map[x0][y0][2]=true Map[x1][y1][3]=true 数三角形的办法 在向后寻找另外两个顶点的时候,如果存 在如图所示的线中的任意一条,则停止. (x2,y2) (x0,y0) (x2-1,y2) ( Map[x0][y0][1] || Map[x0][y0][2] || Map[x0][y0][3] || Map[x2][y2][0] || Map[x2][y2][2] || Map[x2][y2][3] || Map[x2-1][y2][3] ) (x1,y1) 数三角形的办法 如果停止的时候(x1,y1)与(x2,y2)满足条件 (map[x1][y1][2] && !map[x2-1][y2][3]),则 找到一个符合题意的三角形.否则所寻找 的三角形不存在. (x1,y1) (x0,y0) (x2,y2 (x ) 2-1,y2) 数三角形的办法 其他三角形的做法与第一种基本相同
基于线的枚举 基于块的枚举 把小矩形截出来 三角形一定是直角三角形 在三个方向上各挑一条线 小矩形内部没有横线 判断三角形 三角形是否出界 是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,000
9 基于线的枚举 三角形一定是直角三角形 在三个方向上各挑一条线 判断三角形 三角形是否出界 是否被横线割 是否被竖线割 是否被斜线切 三角形是否为空 基于块的枚举 把小矩形截出来 小矩形内部没有横线 和竖线 课堂讨论 三、枚举的顺序和策略 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、完成搜索后返回矩形面积最大值
算法框架 左右剪枝 for(left- 1; left < U; left ++ 利用矩阵左右列关系联系剪枝: 类到的为置歌(都小泡经限到的 for(right- left; right oU & right-left+1 <100; 数《好 算出每一行的最大最小值妆举上下边界求最大子矩 额金會图9是被到 上下剪枝 进一步上下剪枝方法 利用矩阵上下行关系剪枝 处理到当前行 前行不是第 且当前行的 间完全包 ◆如果发现与前面已经得到的子矩阵不能形 成符合条件的子矩阵 则把前面子矩阵中前驱的不符合条件的行 去掉,形成新的包含当前行的符合条件的 如何有效确定上下界 1156算法分析 ◆常量C的取值范围是【0,10】 ◆复杂度n^4但是通过剪枝实际 ◆利用一个数组来记录在该左右边界下,每 的程序比较快 行最高海拔和最低海拔 ◆利用海拔高度进一步剪枝,可 以做到复杂度n^3
10 算法框架 for (left = 1; left <= U; left ++) { for (right = left; right <= U && right – left + 1 <= 100; right ++) { 算出每一行的最大最小值,枚举上下边界求最大子矩 阵; } } 左右剪枝 利用矩阵左右列关系联系剪枝： 1、如果以某列为左边界，不考虑海拔限制的情 况下可以求到的最大面积都小于已经求到的最 大面积，则跳出循环。 2、如果当前区间在上一次可以取到的最大连续 的高度与不考虑海拔可以取到的最大宽的乘积 不大于已经求到的最大面积，则跳出循环。 3、如果上次求到的可以取到的最大连续的高度 与当前区间宽度的乘积小于等于已经求到的最 大面积，则直接越过当前循环。 上下剪枝 利用矩阵上下行关系剪枝： 1、如果当前行不是第一行，并且当前行的 海拔区间完全包含上一行的海拔区间，则 显然当前行不可能构成从上一行开始枚举 的面积，直接越过当前循环 。 进一步上下剪枝方法 处理到当前行 如果发现与前面已经得到的子矩阵不能形 成符合条件的子矩阵 则把前面子矩阵中前驱的不符合条件的行 去掉，形成新的包含当前行的符合条件的 子矩阵 如何有效确定上下界 常量C的取值范围是【0，10】 利用一个数组来记录在该左右边界下，每 行最高海拔和最低海拔。 1156算法分析 复杂度n^4,但是通过剪枝,实际 的程序比较快. 利用海拔高度进一步剪枝，可 以做到复杂度n^3