题目链接: https://www.luogu.com.cn/problem/P1273

题意

给一颗有 n 个节点，其中共有 n-m 个叶子的树。给出经过每一条边所耗费的体力 wi。每个叶子上有一个值 ai，如果能访问到该叶子，那么可以补充 ai 点体力。

你现在从根节点出发，在保证结束后体力值不小于零的情况下，求能够访问到的最多的叶子数。

2≤N≤3000, wi,ai≤10

思路

首先发现这题可以划分成若干个子问题，考虑DP。子问题的划分在树上进行，所以首先它是一个树状DP。

然后就可以写出对于每个子树上的解 dp[u][i] 表示在 u 节点上，访问完 i 个叶子后的剩下体力。

状态转移直接一个分组背包就可以了。非常的简单。

复杂度 O(n^3)。

代码

#include <iostream>
#include <vector>
#include <cstring>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 3e3+5;
int arr[maxN], dp[maxN][maxN];
int n, m;
struct st { int to, w; };
std::vector<std::vector<st>> e;

int init(int u = 1) {
  if (u > n-m) { dp[u][1] = arr[u]; return 1; }
  dp[u][0] = 0;
  int user = 0;
  orep(i, 0ul, e[u].size()) {
    int v = e[u][i].to, w = e[u][i].w;
    int cur = init(v);
    user += cur;
    for(int j = user; j > 0; --j) {
      orep(k, 1, 1+std::min(j, cur)) {
        dp[u][j] = std::max(dp[u][j], dp[u][j-k] + dp[v][k] - w);
      }
    }
  }
  return user;
}

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  std::cin >> n >> m;
  e = std::vector<std::vector<st>>(n+1);
  orep(i, 0, n-m) {
    int k; std::cin >> k;
    orep(j, 0, k) {
      int t, w; std::cin >> t >> w;
      e[i+1].push_back({t, w});
    }
  }
  memset(dp, -0x3f, sizeof(dp));
  orep(i, n-m+1, n+1) { std::cin >> arr[i]; }
  init();
  for(int i = m; i > 0; i--) {
    if (dp[1][i] >= 0) { std::cout << i; return 0; }
  }
}