状态压缩DP 树形D

状态压缩动态规划

    动态规划的状态有时候比较难,不容易表示出来,需要用一些编码技术,把状态压缩的用简单的方式表示出来。典型方式:当需要表示一个集合有哪些元素时,往往利用2进制用一个整数表示。
    *:一般有个数据 n<16 或者 n<32 这个很可能就是状态DP的标志,因为我们要用一个int的二进制来表示这些状态。要注意好这些数据规模的提示作用。
    *:确定了为状态DP,那么第一步就是预处理,求出每行所有可能的状态了,cnt记录总的状态数,stk[]记录所有的可能状态。以炮兵阵地为例:
       int cnt, stk[MAX];
 
       void findStk(int n){     //  求出所有可能的状态。
           for(int i = 0; i < (1<<n); i ++)
              if(ok(i)){                       //  判断这种状态可不可行。
                  stk[cnt] = i;
                  sum[cnt ++] = getSum(i);     //  计算这种状态包含了几个炮兵。
              }
       }
 
       bool ok(int x){          //  判断状态x是否符合,即是否会出现两个大炮间隔小于2。
           if(x & (x<<1)) return false;
           if(x & (x<<2)) return false;
           return true;
       }
 
       int getSum(int x){       //  求出状态x中安装了多少门大炮,x的二进制有几个1。
           int num = 0;
           while(x > 0){
               if(x & 1) num ++;
               x >>= 1;
           }
           return num;
        }
    *:然后就是DP部分了,明确好状态转移方程。先特殊处理第1行,然后按状态转移方程求出剩下的值。
 
经典问题:TSP
    一个n个点的带权的有向图,求一条路径,使得这条路经过每个点恰好一次,并且路径上边的权值和最小(或者最大)。或者求一条具有这样性质的回路,这是经典的TSP问题。
    n <= 16 (重要条件,状态压缩的标志)
    如何表示一个点集:
由于只有16个点,所以我们用一个整数表示一个点集:
例如:
    5 = 0000000000000101;(2进制表示)
    它的第0位和第2位是1,就表示这个点集里有2个点,分别是点0和点2。
    31 = 0000000000011111; (2进制表示)
    表示这个点集里有5个点,分别是0,1,2,4,5;
所以一个整数i就表示了一个点集;整数i可以表示一个点集,也可以表示是第i个点。

    状态表示:
dp[i][j]表示经过点集i中的点恰好一次,不经过其它的点,并且以j点为终点的路径,权值和的最小值,如果这个状态不存在,就是无穷大。
    状态转移:
    单点集:状态存在dp[i][j] = 0;否则无穷大。非单点集:
    1:状态存在  dp[i][j] = min(dp[k][s] + w[s][j])
    k表示i集合中去掉了j点的集合,s遍历集合k中的点并且dp[k][s]状态存在,点s到点j有边存在,w[s][j]表示边的权值。
    2.:状态不存在 dp[i][j]为无穷大。
    最后的结果是: min( dp[( 1<<n ) – 1][j] ) ( 0 <= j < n );
   
    技巧:利用2进制,使得一个整数表示一个点集,这样集合的操作可以用位运算来实现。例如从集合i中去掉点j:
    k = i & (~( 1<<j)) 或者 k = i – (1<<j)
 
 
 

树型动态规划

    树本身就是一个递归的结构,所以在树上进行动态规划或者递推是最合适不过的事情。

    必要条件:子树之间不可以相互干扰,如果本来是相互干扰的,那么我们必须添加变量使得他们不相互干扰。

Party at Hali-Bula

    题目大意:n个人形成一个关系树,每个节点代表一个人,节点的根表示这个人的唯一的直接上司,只有根没有上司。要求选取一部分人出来,使得每2个人之间不能有直接的上下级的关系,求最多能选多少个人出来,并且求出获得最大人数的选人方案是否唯一。

    这是一个经典的树型动态规划,人之间的关系形成树型结构,简单的染色统计是不正确的

    DP部分:用dp[i][0]表示不选择i点时,i点及其子树能选出的最多人数,dp[i][1]表示选择i点时,i点及其子树的最多人数。

    状态转移方程:

    对于叶子节点: 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])

 

    如何判断最优解是否唯一?

    新加一个状态dup[i][j],表示相应的dp[i][j]是否是唯一方案。

    对于叶子结点:dup[k][0] = dup[k][1] = 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

    2:i的任一儿子j有dup[j][0] = 0, 则dup[i][1] = 0

Strategic game

    题目大意:一城堡的所有的道路形成一个n个节点的树,如果在一个节点上放上一个士兵,那么和这个节点相连的边就会被看守住,问把所有边看守住最少需要放多少士兵。

    典型的树型动态规划:

    dproot[ i ]表示以i为根的子树,在i上放置一个士兵,看守住整个子树需要多少士兵。

    all[ i ]表示看守住整个以i为根的子树需要多少士兵。

    状态转移方程:

    叶子节点:dproot[k] =1; all[k] = 0;

    非叶子节点: dproot[i] = 1 + ∑all[j](j是i的儿子);

                 all[i] = min( dproot[i], ∑dproot[j](j是i的儿子) );

    原文作者:671coder
    原文地址: https://blog.csdn.net/liuqiyao_01/article/details/8752034
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞