hiho一下第76周《Suzhou Adventure》题目分析

5
4

题目大意

给定一颗N个节点的树,每个节点有权值W[i],从中选择M个节点,使得这M个节点的权值之和最大。同时满足:

  • 条件一:当一个节点被选择后,它的所有祖先节点也要被选择
  • 条件二:其中有K个节点是必须要选择的


解体思路

本题所考察的算法是树形动态规划。

对于两个附加条件,我们分别进行处理:

条件一:当一个节点被选择后,它的所有祖先节点也要被选择

该条件换一个说法,可以解释为:只有当选择了一个节点后,我们才可以选择它的子节点。

我们首先建立状态f[i][k]f[i][k]表示以i节点为根的子树,在满足条件一的情况下,选择至多k的节点能够得到的最大权值。

则可以写出状态转移情况:

  • 选择i节点:f[i][k]等于w[i]加上所有子节点选择k-1个节点的最大权值
  • 不选择i节点:f[i][k] = 0

不选择i节点很好处理,那么我们如何处理选择i节点时,子节点的情况?

根据题目描述,我们知道给定的节点i可能有多个儿子节点,不妨假设其有m个儿子节点。

则可以表示为,在m个儿子上一共选择k-1个节点,使得选择的节点权值之和最大。

举个例子,比如样例:

样例的树结构

我们在计算f[1][4]时,需要考虑对于以2,3,4分别为根节点子树,一共选择3个节点,来使得权值最大。也就是说在2子树中选择x个节点,3子树中选择y个节点,4子树中选择z个节点,使得x+y+z=3

很显然,该问题同样是一个动态规划问题:

建立状态g[i][j]g[i][j]表示前i个儿子选择j个节点时最大权值,则有状态转移过程:

g[i][j] = max{g[i - 1][j - k] + f[childId][k] | k = 0 .. j}

如果你有做过hiho一下第67期,你会发现这个子问题其实是一个泛化背包问题

因此我们可以得到整个动态规划的过程:

// 初始化f数组
f[][] = -1;

dp(root, k):
    If (k == 0) Then
        Return 0;
    End If
    If (f[root][k] != -1) Then
        // 由于可能多次调用dp(root,k)
        // 所以这里采用了记忆化的思想
        Return f[root][k];
    End If
    // 不选择该节点
    f[root][k] = 0;
    // 选择该节点
    g[][] = 0;  // 初始化g数组,需要注意g为该函数的局部变量
    For i = 1 .. m  // 枚举子节点
        For j = 0 .. k - 1
            For t = 0 .. j
                If g[i][j] < dp(child[i], t) + g[i-1][j-t] Then
                    g[i][j] = dp(child[i], t) + g[i-1][j-t];
                End If
            End For
        End For
    End For
    If (f[root][k] < g[m][k-1] + w[root]) Then
        f[root][k] = g[m][k-1] + w[root];
    End If
    Return f[root][k];


接下来我们处理条件二:其中有K个节点是必须要选择的

因为选择这K个节点,一定会选择它们所有的祖先节点。所以我们不妨先将这个K个节点和其祖先节点标记出来,并统计个数。

我们可以用下面这段代码来标记:

bool must[ N ]; // must[i]表示,该节点是否必须被选择
mark(i):
    must[i] = true;
    While (i != null)
        If (father[i] is not null) Then
            must[ father[i] ] = true;
        Else
        i = father[i];
    End While

最后我们统计所有被标记的节点数量,若其总数大于 M,那么显然是无解的。因为无论怎么选择都会超过 M个节点。

若总数小于等于 M,则表示是有可行解的。那么又有个新的问题:如何保证我们dp的过程中,一定能够把这些标记的点都选上。

我们需要在过程中,将不合法的状态标记出来,使得最后得到解一定是合法的,也就是包含所有必须选择的节点。

比如must[root] = true,那么f[root][0]一定就是一个不合法的状态,因为至少需要k=1,才能把root节点选择上。

我们建立一个标签INVALID来表示这些不合法的状态,改进后的dp函数代码:

// 初始化f数组
f[][] = -1;

dp(root, k):
    If (k == 0) Then
        If (must[root]) Then
            return INVALID;
        End If
        Return 0;
    End If
    If (f[root][k] != -1) Then
        // 由于可能多次调用dp(root,k)
        // 所以这里采用了记忆化的思想
        Return f[root][k];
    End If

    // 不选择该节点
    If (must[ root ]) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = 0;
    End If

    // 选择该节点
    g[][] = 0;  // 初始化g数组,需要注意g为该函数的局部变量
    For i = 1 .. m  // 枚举子节点
        For j = 0 .. k - 1
            g[i][j] = INVALID; // 先假设不合法
            For t = 0 .. j
                If (dp(child[i], t) != INVALID and g[i-1][j-t] != INVALID) Then
                    If (g[i][j] == INVALID or g[i][j] < dp(child[i], t) + g[i-1][j-t]) Then
                        g[i][j] = dp(child[i], t) + g[i-1][j-t];
                    End If
                End If
            End For
        End For
    End For

    If (g[m][k-1] == INVALID) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = g[m][k-1] + w[root];
    End If

    Return f[root][k];

另外还有一种比较取巧的方法:

由于我们动态规划得到的结果一定是最大解,所以我们只需要让最大解一定会选择这些must[i]=true的节点即可。

所以我们不妨给must[i]=true的节点加上一个很大的权值MOD。由于本题中w[i]不超过100,节点数量也不超过100,最大可能的解也就不超过10000。因此我们我们不妨设MOD = 1000000

这样在不改变dp函数情况下得到的解f[1][M],只要进行一次模运算,即f[i][M] % MOD就是该题实际的解了。


最后我们再来总结一下本题的解题过程:

  1. K个必须经过的节点执行mark()函数;
  2. 统计被标记为true的节点数量,若大于M则返回-1
  3. 若采用增加权值的方法,则对被标记为true的节点,权值增加MOD;否则直接进行第4步;
  4. 执行dp(1,M),得到f[1][M]

2 answer(s)

0

我觉得上面的伪代码有点问题。在最后更新f[root][k]时:

If (g[m][k-1] == INVALID) Then
        f[root][k] = INVALID;
    Else
        f[root][k] = g[m][k-1] + w[root];
    End If

这只是选择root的时候,并没有考虑如果不选择该root节点的情况。 实际上,如果此时g[m][k-1] == INVALID,而且must[root]==false,那么f[root][k]可以为0,而不是必须为INVALID. 按照这个思路改了代码后,也AC了。改后的代码如下:

If (g[m][k-1] == INVALID) Then
        pass
    Else
        f[root][k] = g[m][k-1] + w[root];
    End If
4

可以把关键点到根的路径上的所有点直接缩到根上,接下来就是一个很简单的 DP 了

  • 我也是这么做的,比上面说的做法简单太多了

  • 如果全部压缩到根上,那意味着还需要改变树的结构吧?也需要找到被标记的节点路径上的最深的节点,感觉不一定比这个方法简单多少...

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享