经典树型DP状态压缩DP入门.ppt
《经典树型DP状态压缩DP入门.ppt》由会员分享,可在线阅读,更多相关《经典树型DP状态压缩DP入门.ppt(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、经典入门经典入门树型动态规划和状态压缩动态规划树型动态规划和状态压缩动态规划n百度文库不能允许上传同样的,所以我在这里改改 财富值为零,请随便下载树型动态规划树型动态规划n什么是树型动态规划:n树本身就是一个递归的结构,所以在树上进行动态规划或者递推是在合适不过的事情。n必要条件:子树之间不可以相互干扰,如果本来是相互干扰的,那么我们必须添加变量使得他们不相互干扰。Party at Hali-Bulan题目大意:nn个人形成一个关系树,每个节点代表一个人,节点的根表示这个人的唯一的直接上司,只有根没有上司。要求选取一部分人出来,使得每2个人之间不能有直接的上下级的关系,求最多能选多少个人出来,
2、并且求出获得最大人数的选人方案是否唯一。n这是一个经典的树型动态规划。Party at Hali-Bula n简单的染色统计是不正确的Party at Hali-Bulan人之间的关系形成树型结构nDP,用dpi0表示不选择i点时,i点及其子树能选出的最多人数,dpi1表示选择i点时,i点及其子树的最多人数。Party at Hali-Bulan状态转移方程:p对于叶子节点 dpk0=0,dpk1=1p对于非叶子节点i,pdpi0=max(dpj0,dpj1)(j是i的儿子)pdpi1=1+dpj0(j是i的儿子)n最多人数即为max(dp00,dp01)n如何判断最优解是否唯一?Party
3、at Hali-Bulan新加一个状态dupij,表示相应的dpij是否是唯一方案。n对于叶子结点,dupk0=dupk1=1.n对于非叶子结点,p对于i的任一儿子j,若(dpj0 dpj1 且 dupj0=0)或(dpj0 dpj1 且 dupj1=0)或(dpj0=dpj1),则dupi0=0p对于i的任一儿子j有dupj0=0,则dupi1=0Strategic game n题目大意:n一城堡的所有的道路形成一个n个节点的树,如果在一个节点上放上一个士兵,那么和这个节点相连的边就会被看守住,问把所有边看守住最少需要放多少士兵。n典型的树型动态规划Strategic gamendproot
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典 DP 状态 压缩 入门
限制150内