算法设计chapter1-2.pptVIP

1193 Up the Stairs 题目大意： N个人，F级楼梯，从0级搬货物到F级 一人只能搬一件，每一级楼梯时间为1 第0级（即地板）有B件货物 N个人的初始状态不一定在地板，可能在某级，并有两种可能状态：搬着东西上去，或刚搬完正在走下来 拿放货物不需要时间 要多久才能将地板的货物全部搬上去 1193 Up the Stairs 解题思路： 碰撞时两人交换速度,也可看成两人继续向原来的方向行进 可以独立的考虑每个人的搬运活动 KISS：可以二分答案 Tips What is 二分？ Example 1 4 5 8 9 10 12 15 1 4 5 8 1 4 4 两个主要元素：布尔查询，区段 第一章作业 1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈 1021 Couples 题目大意： N对夫妇坐成一圈 如果某对夫妇挨着坐将被从圈中移走 重复以上操作 问最后会不会全部被移走 如1 3是一对，2 4是一对 如果1 3 2 4（4与1相邻）则 YES 如果1 2 3 4（4与1相邻）则 NO 1021 Couples 解题思路 无解的情况，互相嵌套 ……a….b….a….b….. 类似于括号匹配，可将n对夫妇看成n种括号 用一个栈来模拟，将括号逐个push到栈里 当栈顶存在匹配对时进行pop操作 看最后栈顶是否为空 1021 Couples 如样例： 4 1 4 2 3 5 6 7 8 1 2 3 4 5 6 7 8 1021 Couples 如样例： 2 1 3 2 4 1 2 3 4 第一章作业 1198 SubString 8!穷举 题目短 1029 Rabbit 递推 简单 1028 梵塔问题 - 分治，归纳 - 有意思但数据规模较大 1193 递推 较难 1021 简单题 - 规模原来很大 - 难 - 栈 1176 Two Ends 1176 Two Ends 题目大意 给定偶数项的数列，轮流从两端取。 玩家一允许任意策略，玩家二采用贪心策略（每次取两端大者） 最终根据取数的总和大小判断胜负 问玩家一最多能赢多少分？ 1176 Two Ends 与上课课件上面的题目类似 问题不一样，解法不一样 解法 二维状态的动态规划 算法时间复杂度O(n2) 第二章作业 1150 简单魔板 1151 魔板 1515 魔板C 1007 数组与下标（二维数组） 简单 1036 数组与下标（二维数组） 简单 1027 简单 1006 栈与回溯 简单 5!搜索 1156 深搜 指针 简单 树的遍历 1034 队列与搜索 1150 1151 1515 魔板 题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 1 2 3 4 5 6 7 8 1150 1151 1515 魔板 题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 每行循环右移一格 1 2 3 4 5 6 7 8 1150 1151 1515 魔板 题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 每行循环右移一格 中间四块顺时针转一格 1 2 3 4 5 6 7 8 1150 1151 1515 魔板 题目大意 魔板是2行4列的方格，八格分别标为1-8 初始状态为1 2 3 4 8 7 6 5 有三种操作： 上下两行互换 每行循环右移一格 中间四块顺时针转一格 给定一个终止状态，求最小操作数及方案 1 2 3 4 5 6 7 8 1 2 4 5 6 7 8 3 1150 1151 1515 魔板 解题思路 对模板进行状态搜索 由一种状态可以转移到另外三种状态，搜索树为一棵三叉树 在这棵三叉树上搜索，目的是求出最优解 1150 1151 1515 魔板 算法一：盲目DFS 对这棵三叉树进行DFS 若想求得最优解，需要遍历整棵树 需要进行重复扩展 优化： 若已找到一个可行解，可剪去大于等于这个深度的所有子树 评价： 效果： 加优化后勉强可过1150 很傻很天真 1150 1151 1515 魔板 算法二：BFS 对这棵三叉树进行BFS 第一个可行解即