题解：P12136 [蓝桥杯 2025 省 B] 生产车间

gu51yo · 2025-04-17 22:38:38 · 题解

组合问题，观察到数据范围 1000，考虑树形 DP。因为每个节点的可能提供的值不确定，所以还需要利用分组背包来实现。

思路分析

状态定义

定义 dp[u] 为 bitset 类型。例如 dp[u][x] = true 表示在以节点 u 为根的子树中，通过删除部分节点，可以使得子树提供恰好 x 的价值。

状态转移

采用树形 DP 的经典形式，DFS，从叶子节点开始，自底向上。

• 叶子节点：

  只有两种状态。保留或删除，向父节点贡献 w[u] 或 0 价值。

• 非叶子节点：

  有多种状态，状态集合即它可能贡献的价值。设 u 的子节点集合为 g(u)。dp_u 即 u 的子节点 v 们的价值组合集合。

  再递归向上，直到根节点。这就是一个树上的，分组背包问题了。我们可以维护一个 bitset 来高效地解决这个问题。

时间复杂度

• DFS 遍历整棵树需要 O(n) 时间。在每个非叶子节点 u，我们需要对其子节点 v 的价值集合进行组合。总时间复杂度为 O(n \cdot W^2)。

  对于 n=1000,W=1000，理论时间复杂度是 10^9，但因为终止条件 s+f \leq w[u] 会节省很多计算。实测运行效率远好于理论上界，即使不解绑同步，依然可以 200ms 通过此题。

• 实际上可以用位运算优化来降低时间复杂度。感谢 MattL 提出。同时感谢 Dr_Gilbert 的多次审核。

      for (int s = 0; s <= w[u]; s++) if (cur[s] == 1)    // 分组背包 DP, 未优化，O(W^2)
          for (int f = 0; s + f <= w[u]; f++)
              if (dp[v][f] == 1) nxt[s + f] = 1;

  for (int i = 0; i <= w[u]; ++i) mask.set(i); // mask存节点u的所有合法值
  ...
  ...
  for (int s = cur._Find_first(); s <= w[u]; s = cur._Find_next(s)) nxt |= (dp[v] << s);
  nxt &= mask;  // 避免位运算后出现非法值，&一下。位运算优化后，时间复杂度常数可以除以64。

具体实现详细见代码：

const int N = 1e3+9;
int n, ans=0;
vector<int> w(N);
vector<vector<int>> g(N);
vector<bitset<N>> dp(N);

void dfs(int u, int p) {
    if (g[u].size() == 1 && p != -1) {  // 叶子节点判断
        dp[u][0] = 1;
        if (w[u] <= N) dp[u][w[u]] = 1;
        return;
    }

    bitset<N> cur, mask; cur[0] = 1;
    for (int i = 0; i <= w[u]; ++i) mask.set(i);

    for (int v : g[u]) if (v != p) {
        dfs(v, u);
        bitset<N> nxt; nxt[0] = 1;
        for (int s = cur._Find_first(); s <= w[u]; s = cur._Find_next(s)) nxt |= (dp[v] << s);
        nxt &= mask;
        cur = nxt;
    }
    dp[u] = cur;
}

signed main () {
    cin >> n;   // 输入
    for (int i = 1; i <= n; i++) cin >> w[i];   
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }

    dfs(1, -1); // 树形 DP

    for (int x = w[1]; x >= 0; x--) if (dp[1][x] == 1) {ans = x; break;}    // 输出
    cout << ans << '\n';
}

值得一提的是，这可能是一道假题。因为题目并没有提到“若将 u 的所有子节点都删除后，u 不会因为转变为叶子节点而转变为产出材料”。