动态规划进阶2教学课件.ppt

状态定义 如果按顺序放置长方形块，每个块放置的选择只与上一行的占用与否的情况有关。 将一行中每个各自的占用与否作为状态，可以进行状态压缩。 状态转移 考虑相邻两行的两个状态。 复杂度计算 轮廓线DP 改变状态定义，状态中出现的不一定是完整的行，而是以某一个位置分界的轮廓线。 状态转移 状态转移时，只需要考虑轮廓线发生变化的一个位置。 轮廓线DP的优势 更多的问题 如果压缩时每个维度大于2怎么办？ k进制存储：慢，省空间。 将k扩展到最近的2整次幂：快，浪费空间。 状压DP问题的思路 首先确定是否可能有可以压缩的状态。 关键标志：题目里有一维特别小的数据。 一般能表示为一个小整数数组的状态都可以状压。 二维期盼问题考虑用轮廓线的方法简化转移。 动态规划求解。 “ ” 动态规划进阶 概率论基础知识 会算就好= = 样本空间 1 2 3 4 5 随机事件 1 2 3 4 5 互斥事件 什么是概率？ 概率的计算 条件概率 古典概型和几何概型 随机变量 将样本空间里所有的样本点映射在实数集上就得到了随机变量。如果随机变量的取值是有限或者可数的，那那么称这个随机变量为离散随机变量，否则为连续随机变量。 例如掷一个色子得到的点数就是一个离散随机变量，打靶时一次射击距离靶心的距离就是一个连续随机变量。 数学期望 数学期望的性质 概率DP问题 涉及概率和数学期望的动态规划 简单的问题 简单的问题 成环了~~~~~~~~ 解决成环问题 更为棘手的问题 用到了之前的状态！ 解决方案 解决方案 求解概率DP问题的思路 列出状态转移方程。 用到以前的状态？待定系数转化为用到当前状态 用到当前状态？小学算数移项 用普通DP方法求解 状态压缩的DP问题 表示复杂状态 为何需要状态压缩？ 有时我们定义的状态中难免出现一些奇怪的东西。 一个选择集合？ 一个行或者列？ 然而，我们只能用整数来作为数组的下标。 状态压缩：将复杂状态表示为整数。 经典问题 动态规划做法 如何表示一个子集？ … 5 4 3 2 1 … 1 0 0 1 1 简单的位运算 运算符 作用 A B Q 与 1010 1100 1000 | 或 1010 1100 1110 ^ 异或 1010 1100 0110 ~ 非 1010 0101 左移 1010 2 101000 右移 1010 2 10 补0 有符号：补符号位 无符号：补0 位运算实例 取第k位：(xk)1 设置第k位为1：x|=1k 设置第k位为0：x=~(1k) 翻转第k位：x^=1k POJ 2411 Mondriaans Dream “ ”