树形DP,和背包差不多。dp[now][x]表示now这个节点的子树上,花费为x的时候,获得的最大防御能力(保证敌方HP<=0)
#include#include #include #include using namespace std;const int maxn = 1000 + 10;int T, n, m;vector tree[maxn];struct kind{ int price; int power; kind(int a, int b){ price = a; power = b; }};vector v[maxn];bool vis[maxn];int dp[maxn][200 + 10];int flag[200 + 10], tmp[200 + 10];void init(){ for (int i = 0; i <= n; i++) tree[i].clear(); for (int i = 0; i <= n; i++) v[i].clear(); memset(vis, 0, sizeof vis); memset(dp, -1, sizeof dp);}void read(){ scanf("%d", &n); for (int i = 1; i <= n - 1; i++) { int u, v; scanf("%d%d", &u, &v); tree[u].push_back(v); tree[v].push_back(u); } scanf("%d", &m); for (int i = 1; i <= n; i++) { int ki; scanf("%d", &ki); while (ki--) { int pricei, poweri; scanf("%d%d", &pricei, &poweri); kind k(pricei, poweri); v[i].push_back(k); } }}void dfs(int now){ bool fail = 1; for (int i = 0; i = v[now][i].price; j--) if (flag[j - v[now][i].price] != -1) dp[now][j] = max(dp[now][j], flag[j - v[now][i].price] + v[now][i].power); for (int i = 0; i <= m; i++) dp[now][i] = max(dp[now][i], flag[i]); for (int i = 0; i