P4362 [NOI2002] 贪吃的九头龙 题解

2021年11月24日 阅读数:2
这篇文章主要向大家介绍P4362 [NOI2002] 贪吃的九头龙 题解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Description

Luogu传送门node

Solution

很是巧妙地树形 \(dp\),刚开始彻底不知道如何设状态 QwQ。c++

言归正传,咱们对于每一个点能够随便分配个某一个头,只有大头须要必须有 \(k\) 个果子,因此咱们的状态里只须要大头就够了。git

那么设 \(dp_{x, i}\) 表示以 \(x\) 为根的子树中给大头 \(i\) 个果子最小的难受值。数组

可是咱们发现根本无法转移,因此考虑再多记录一点东西。spa

设:\(dp_{x, i, 0/1}\),0/1 表示 \(x\) 节点是否分给大头,那么就有转移方程:code

\[dp_{x, i, 0} = min\{ dp_{y, j, 0} + dp_{x, i - j, 0} + (m == 2) \times edge_{x, y},\ \ dp_{y, j, 1} + dp_{x, i - j, 0}\} \]

解释一下:ip

  • 第一项:\(x\) 和它的一个儿子 \(y\) 都不给大头,那么就得把它们分给其余不一样的头,但若是此时 \(m = 2\),即除了大头只有一个头,那就只能加上边的难受值了。
  • 第二项:\(y\) 给大头,\(x\) 不给大头,\(edge_{x, y}\) 没有贡献。

再来看 \(dp_{x, i, 1}\) 的转移:get

\[dp_{x, i, 1} = min\{dp_{y, j, 1} + dp_{x, i - j, 1} + edge_{x, y},\ \ dp_{y, j, 0} + dp_{x, i - j, 1} \} \]

这个就比较好理解了吧,跟上面的差很少,很少解释了。it

可是直接转移会有问题,由于在同一轮转移过程当中 \(dp\) 数组的值是不能变的,否则就有问题,因此转移前先给它转存一下,\(f_{i, 0/1} = dp_{x, i, 0/i}\),而后用 \(f_{i, 0/1}\) 去转移。io

再放一遍方程吧:

\[dp_{x, i, 0} = min\{ dp_{y, j, 0} + f_{i - j, 0} + (m == 2) \times edge_{x, y},\ \ dp_{y, j, 1} + f_{i - j, 0}\} \]

\[dp_{x, i, 1} = min\{dp_{y, j, 1} + f_{i - j, 1} + edge_{x, y},\ \ dp_{y, j, 0} + f_{i - j, 1} \} \]

Code

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 310;
int n, m, k;
struct node{
    int v, w;
};
vector <node> g[N];
int head[N], tot;
int dp[N][N][2], f[N][2];

inline void dfs(int x, int fa){
    dp[x][0][0] = dp[x][1][1] = 0;
    for(auto nxt : g[x]){
        int y = nxt.v;
        if(y == fa) continue;
        dfs(y, x);
        memcpy(f, dp[x], sizeof(dp[x]));
        memset(dp[x], 0x3f, sizeof(dp[x]));
        for(int i = 0; i <= k; ++i)
            for(int j = 0; j <= i; ++j){
                dp[x][i][0] = min(dp[x][i][0], min(dp[y][j][0] + f[i - j][0] + (m == 2) * nxt.w, dp[y][j][1] + f[i - j][0]));
                dp[x][i][1] = min(dp[x][i][1], min(dp[y][j][1] + f[i - j][1] + nxt.w, dp[y][j][0] + f[i - j][1]));
            }
    }
}

int main(){
    n = read(), m = read(), k = read();
    if(n - k < m - 1) return puts("-1"), 0;
    for(int i = 1; i < n; ++i){
        int u = read(), v = read(), w = read();
        g[u].push_back((node){v, w});
        g[v].push_back((node){u, w});
    }
    memset(dp, 0x3f, sizeof(dp));
    dfs(1, 1);
    printf("%d\n", dp[1][k][1]);
    return 0;
}

\[\_EOF\_ \]