经典树型DP状态压缩DP入门.ppt

经典入门 树型动态规划和状态压缩动态规划 百度文库不能允许上传同样的 所以我在这里改改财富值为零 请随便下载 树型动态规划 什么是树型动态规划 树本身就是一个递归的结构 所以在树上进行动态规划或者递推是在合适不过的事情 必要条件 子树之间不可以相互干扰 如果本来是相互干扰的 那么我们必须添加变量使得他们不相互干扰 PartyatHali Bula 题目大意 n个人形成一个关系树 每个节点代表一个人 节点的根表示这个人的唯一的直接上司 只有根没有上司 要求选取一部分人出来 使得每2个人之间不能有直接的上下级的关系 求最多能选多少个人出来 并且求出获得最大人数的选人方案是否唯一 这是一个经典的树型动态规划 PartyatHali Bula 简单的染色统计是不正确的 PartyatHali Bula 人之间的关系形成树型结构DP 用dp i 0 表示不选择i点时 i点及其子树能选出的最多人数 dp i 1 表示选择i点时 i点及其子树的最多人数 PartyatHali Bula 状态转移方程 对于叶子节点dp k 0 0 dp k 1 1对于非叶子节点i dp i 0 max dp j 0 dp j 1 j是i的儿子 dp i 1 1 dp j 0 j是i的儿子 最多人数即为max dp 0 0 dp 0 1 如何判断最优解是否唯一 PartyatHali Bula 新加一个状态dup i j 表示相应的dp i j 是否是唯一方案 对于叶子结点 dup k 0 dup k 1 1 对于非叶子结点 对于i的任一儿子j 若 dp j 0 dp j 1 且dup j 0 0 或 dp j 0 dp j 1 且dup j 1 0 或 dp j 0 dp j 1 则dup i 0 0对于i的任一儿子j有dup j 0 0 则dup i 1 0 Strategicgame 题目大意 一城堡的所有的道路形成一个n个节点的树 如果在一个节点上放上一个士兵 那么和这个节点相连的边就会被看守住 问把所有边看守住最少需要放多少士兵 典型的树型动态规划 Strategicgame dproot i 表示以i为根的子树 在i上放置一个士兵 看守住整个子树需要多少士兵 all i 表示看守住整个以i为根的子树需要多少士兵 Strategicgame 状态转移方程 叶子节点 dproot k 1 all k 0 非叶子节点 dproot i 1 all j j是i的儿子 all i min dproot i dproot j j是i的儿子 这个题目还是比较简单的 如果把题目中看守边变成看守相邻的点呢 留给你来思考 状态压缩动态规划 状态压缩动态规划 动态规划的状态有时候比较恶心 不容易表示出来 需要用一些编码技术 把状态压缩的用简单的方式表示出来 典型方式 当需要表示一个集合有哪些元素时 往往利用2进制用一个整数表示 经典问题 TSP 一个n个点的带权的有向图 求一条路径 使得这条路经过每个点恰好一次 并且路径上边的权值和最小 或者最大 或者求一条具有这样性质的回路 这是经典的TSP问题 n 16 重要条件 状态压缩的标志 今天讲第一个问题的状态压缩动态规划的解法 第2个问题大同小异 TSP 如何表示一个点集 由于只有16个点 所以我们用一个整数表示一个点集 例如 5 0000000000000101 2进制表示 它的第0位和第2位是1 就表示这个点集里有2个点 分别是点0和点2 31 0000000000011111 2进制表示 表示这个点集里有5个点 分别是0 1 2 4 5 TSP 所以一个整数i就表示了一个点集 整数i可以表示一个点集 也可以表示是第i个点 状态表示 dp i j 表示经过点集i中的点恰好一次 不经过其它的点 并且以j点为终点的路径 权值和的最小值 如果这个状态不存在 就是无穷大 TSP 状态转移 单点集 状态存在dp i j 0 否则无穷大 非单点集 状态存在dp i j min dp k s w s j k表示i集合中去掉了j点的集合 s遍历集合k中的点并且dp k s 状态存在 点s到点j有边存在 w s j 表示边的权值 状态不存在dp i j 为无穷大 TSP 最后的结果是 min dp 1 n 1 j 0 j n 技巧 利用2进制 使得一个整数表示一个点集 这样集合的操作可以用位运算来实现 例如从集合i中去掉点j k i 1 j 或者k i 1 j 习题 树型动态规划nkoj1791PartyatHali Bulankoj1678Strategicgamenkoj1794BribingFIPA 需要2重dp poj1946RebuildingRoads 需要2重dp 状态压缩动态规划nkoj1068IslandsandBridgespoj3229TheBestTravelDesignpoj1038BugsIntegrated Inc Thankyou 借用了roba的PartyatHali Bula的ppt感谢tju的roba 数学科学学院06级基础数学描述集合论方向汪方id wangfangbob邮箱 xiaofangbob