枚举 ◆要求在字典中选择一个或者两个单词 ◆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 66 Š 要求在字典中选择一个或者两个单词 „ 所用的所有字母都在字母表中出现 „ 每个字母出现的次数不超过字母表中规定的 次数限制 „ 每个单词的字母个数满足至少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