插头DP初探

Author Avatar
Sakits 7月 17, 2018

基于连通性状态压缩的动态规划问题

简介

  插头DP即基于连通性状态压缩的动态规划问题,连通是图论中一个非常重要的概念。在一个无向图中,如果两个顶点之间存在一条路径,则称这两个点连通。而基于连通性状态压缩的动态规划问题与图论模型有着密切的关联,比如后文涉及到的哈密尔顿回路、生成树等等。通常这类问题的本身与连通性有关或者隐藏着连通信息。

插头

  一个格子某个方向的插头存在表示这个格子在这个方向与相邻格子相连。

轮廓线

  已决策格子与未决策格子的分界线。
  轮廓线上方与其相连的有n+1n+1个插头,包括nn个下插头和11个右插头。

例题

例1 Eat the Trees hdu1693

  求不经过障碍点的哈密顿回路(可多条)方案数。
  这题即求每个非障碍点度数为22,障碍点度数为00的方案数。
  由于这题可以有多条路径,所以不需要对插头进行标号,直接把所有插头当成一样的即可,即有插头为11,无插头为00
  因为非障碍点度数为22,所以每个点都必须有两个插头。
  先考虑非障碍点:

  情况1:没有左插头和上插头

    因为度数必须为22,所以得添加一个下插头和右插头,状态两位都改成11

  情况2:只有一个左插头或上插头

    可以添加一个右插头或一个下插头,状态任意一位改成11

  情况3:既有左插头又有上插头

    直接合并即可,状态两位都改成00

例2 Formula 1 URAL - 1519

  求不经过障碍点的哈密顿回路(只能一条)方案数。
  这题即求每个非障碍点度数为22,障碍点度数为00的方案数,但只能在最后一个空格形成回路。
  怎么知道有没有形成回路呢,其实只有当且仅当对应插头合并的时候会形成一条回路,所以这时候我们就得区分插头了,有两种区分的方法。


  最小表示法

    将对应的插头标为相同的号,但一种情况可能有多种标法,所以采用最小表示法,每次先用O(n)O(n)的时间求出最小表示,再存入状态。
    因为每次存入状态前都需要O(n)O(n)的时间,故这种方法的常数较大,但是转移处理相对简单,并且具有通用性。

  括号表示法

    可以发现插头两两匹配且互不相交,所以我们可以考虑用括号序列来表示一个状态。
    这种做法只有在合并两个插头的时候才需要多余的O(n)O(n)的时间,故常数较小,速度非常优秀。但是代码复杂度较高,转移情况较多,通用性不高。通用性较高的方法有广义括号表示法,但是代码复杂度就又高了一个层次,较为繁琐。


  运用这两种区分方法之后,比上题多了一种情况:当两个相同标号的插头只能在最后一个格子合并。

例3 Beautiful Meadow ZOJ - 3213

  求权值最大的一条哈密顿路径。
  这题即求有两个点度数为11,其他点度数为2200的最大权路径。
  其实就是多了一种度数为11的点,要在什么时候添加这种度数为11的插头呢。
  可以发现要造成一个度数为11的插头,只需要在无左上插头的时候单独插一个插头,或者在只有一个左插头或者上插头的时候把这个插头变成单独一个插头即可。
  并且此题不能够合并同标号插头,否则会造成回路。
  md这题多组数据mp没清零查了5h5h,因为DP的时候查能不能走会越界…