回溯形树状 DP

一个月没上语文课还是不太好……

这篇文章内容不难,但可以帮助我们重新整理对回溯形树状 DP 的思路.

什么叫“回溯形树状 DP”?我们来看一道例题:

Apple Tree ——POJ 2486

有一颗苹果树,每个节点上面有不同数量的苹果,从一个节点到另外一个可以到达的节点花费 步,求 步最多能吃到多少苹果.起始点为 ,可以不回到起始点.

我们会自然地想到:设置 数组,表示在以 为根的子树(以后用 表示)中,从 出发,行走 步,吃到的最多苹果数.不过,仔细思考可以发现,考虑节点 ,在进入到它的子树后是否返回子树的根节点,对统计结果是会有影响的.于是,我们可以考虑多加一维,表示向下行走后是否返回当前结点.

这样,我们重新定义数组 ,表示 中,从根节点开始行走 步,吃到的最多苹果数,其中, 表示不需回到根节点, 表示需要回到根节点.我们最终需要得到

在这篇文章里,我们把像这样在树形 DP 过程中需要考虑是否返回的问题叫做“回溯形树状 DP”.

现在我们考虑:如何求 数组的递推式?我们先给出答案:

对于 ,我们有:

其中, 的子节点, 表示额外分给 的步数.对于第一行,;对于后两行,

很明显,在实际操作中,若要得到 ,我们需要枚举 .接下来我们详细地分析一下这个方程.

我们倒着来,先看第三行.它表示的是要求返回根结点时的情况.我们已经把 步分配给了 ,那么剩下的子树还剩 步,并且要返回到根节点;再看 ,由于我们要花一步到达 ,再花一步从 返回 ,所以实际上 只会得到 步.这就是 的来历.对所有结果取最大值,我们就得到了第三行方程.

然后看前两行,它们代表不需返回根节点的情况.类似地分析,可以发现:

  • 第一行表示先进入其它子树中并返回,然后 中,不再返回.这时 实际分得的步数为
  • 第二行表示先进入 中并返回,然后进入其它子树中,不再返回.这时 分得的步数为

这都是与上述方程相符的.至此,整个 数组就被我们分析完了.不过,还有一些疑点:为什么上面的 就表示除 之外的其它子树?另外,边界是什么?该按照什么顺序求解这个数组?

我们需要理解这道题的具体实现.树形 DP 常常使用 DFS 求解,下面,我们看看这道题的 dfs 函数:

void dfs(int root, int father) {  
  for (int i = head[root]; i != -1; i = edge[i].next) {  
    int son = edge[i].v;  
    if (son == father) continue;  
    dfs(son, root);
    for (int j = s; j >= 1; j--) {
      for (int k = 1; k <= j; k++) {  
        dp[root][j][0] = max(dp[root][j][0], dp[root][j-k][1] + dp[son][k-1][0]); 
        if (k > 1) { 
          dp[root][j][0] = max(dp[root][j][0], dp[root][j-k][0] + dp[son][k-2][1]);  
          dp[root][j][1] = max(dp[root][j][1], dp[root][j-k][1] + dp[son][k-2][1]); 
        }
      }  
    }  
  }  
}

这一块代码似乎很难理解消化.为了便于解释,我们把上面的代码去粗取精:

dfs(root) {  
  for each son of root {  
    dfs(son);
    for (int j = s; j >= 1; j--)
      for (int k = 2; k <= j; k++)
        dp[root][j][1] = max(dp[root][j][1], dp[root][j-k][1] + dp[son][k-2][1]);
  }
}

现在我们针对下面的子树,一步一步分析.

a tree

我们从 开始枚举.首先我们对 执行 DFS 操作,这就得到了所有和 有关的信息.

然后,我们枚举 ,即 所分得的步数.(不难发现这是有用的,因为我们待会儿要用到 的这些信息.)

接着对于每个 枚举 ,即分给子树的步数,并根据方程式 进行计算.不过等等,枚举 的时候是递减的,,这时的 不是还为 么?

不要着急,我们接着往下看.当我们枚举到 时,还会再算一次 .这时的 就不为 了,因为在枚举 ,步数为 时,我们已经给 赋了一个值.当然,这个值只包含了 的贡献.那么,这时就会有:

即为进入 后返回,再进入 后返回,共花 步,吃到的最多苹果数.但别忘了,我们要枚举分给子树的步数,并把结果与当前的 求最大值.因此,在枚举过 后, 就会出现两种情况:

  1. 如果能找到更大的答案,则存储的就是进入 再进入 的最多苹果数.
  2. 如果没有更大的答案,则存储的就是只进入 得到的最多苹果数.

还有一种可能,就是只进入 .这个算法包含了这种可能么?包含了.当我们把 步全部分给 时,就是只进入 的情况.它包含在情况 1 中.

综上,所有的情况都考虑到了.因此,至少当枚举完 时,这个算法是没有问题的.那么,以后的操作就十分类似了:当枚举 时, 仅包括 的贡献.然后,通过枚举给 的步数,我们找到了此时 的最优值.以此类推,当枚举完所有子树时,我们就得到了把 步分给下面的子树,能摘到的最多苹果数.

回头想想,这个问题很像 01 背包——从这行代码就能看出来:

for (int j = s; j >= 1; j--)

实际上,这里确实有 01 背包的思想: j-- 保证了数组中当前位置前的数还是上一步的状态,而我们需要它们来推出这一步的状态.在上面的代码中,这种实现方式是极为重要的.

至于初值,我们可以给 数组中的每个值赋为其描述的子树的根节点上的苹果数——无论如何这都是最少能摘到的苹果数,而它作为边界条件也是有效的.

实际上,这个 j-- 的代码不仅适合于回溯形树状 DP,还适合于所有将某样东西分给子节点,求最优方案的问题——不仅仅是步数。

留下评论

你的邮箱不会被公开。必填部分已用 * 标记。点击查看帮助。

正在加载...
支持 Markdown 语法
回到顶部 ↑