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

《经典树型DP状态压缩DP入门》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、经典入门树型动态规划和状态压缩动态规划百度文库不能允许上传同样的,所以我在这里改改财富值为零,请随便下载树型动态规划什么是树型动态规划：树本身就是一个递归的结构，所以在树上进行动态规划或者递推是在合适不过的事情。必要条件：子树之间不可以相互干扰，如果本来是相互干扰的，那么我们必须添加变量使得他们不相互干扰。PartyatHali-Bula题目大意：n个人形成一个关系树，每个节点代表一个人，节点的根表示这个人的唯一的直接上司，只有根没有上司。要求选取一部分人出来，使得每2个人之间不能有直接的上下级的关系，求最多能选多少个人出来，并且求出获得最大人数的选人方

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[

3、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]

4、城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。典型的树型动态规划Strategicgamedproot[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的儿子

5、))；这个题目还是比较简单的，如果把题目中看守边变成看守相邻的点呢？留给你来思考^_^状态压缩动态规划状态压缩动态规划：动态规划的状态有时候比较恶心，不容易表示出来，需要用一些编码技术，把状态压缩的用简单的方式表示出来。典型方式：当需要表示一个集合有哪些元素时，往往利用2进制用一个整数表示。经典问题：TSP一个n个点的带权的有向图，求一条路径，使得这条路经过每个点恰好一次，并且路径上边的权值和最小（或者最大）。或者求一条具有这样性质的回路，这是经典的TSP问题。n<=16(重要条件,状态压缩的标志)今天讲第一个问题的状态压缩动态规划的解法，第2个问题大同

6、小异。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状态转移：单点集

7、：状态存在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<

8、tHali-Bulankoj1678Strategicgamenkoj1794B