树形依赖背包板子题
树形依赖背包大概就是说:对于一个点,只有选了它的父亲才能选自身
把dfs序建出来,倒过来考虑
设$f[i][j]$表示从第$i$个节点往后背包体积为$j$的最大价值
转移的时候,只有选了该点才能从子树中转移而来
$f[i][j] = max(f[i + 1][j - w[i]] + val[i], f[i + siz[rev[i]]][j]);$
#include<bits/stdc++.h> using namespace std; const int maxn = 3001, inf = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, w[maxn], val[maxn], siz[maxn], rev[maxn], f[maxn][maxn], tot = 0; vector<int> v[maxn]; void dfs(int x, int _fa) { rev[++tot] = x; siz[x] = 1; for(int i = 0, to; i < v[x].size(); i++) { if((to = v[x][i]) == _fa) continue; dfs(to, x); siz[x] += siz[to]; } } main() { n = read(); m = read(); for(int i = 1; i <= n; i++) val[i] = read(), w[i] = 1; for(int i = 1; i <= n; i++) { int x = read(), y = read(); if(x == 0) continue; v[x].push_back(y); v[y].push_back(x); } dfs(1, 0); for(int i = n; i >= 1; i--) { for(int j = 0; j <= m; j++) { f[i][j] = f[i + siz[rev[i]]][j]; if(j >= w[i]) f[i][j] = max(f[i][j], f[i + 1][j - w[rev[i]]] + val[rev[i]]); // printf("%d %d %d\n", i, j, f[i][j]); } } cout << f[1][m]; } /* */
如对本文有疑问, 点击进行留言回复!!
Qt——BUG:构造函数中new了控件并隐藏了,后续显示时位置不对?
PAT甲级 1087. All Roads Lead to Rome (30) (dijkstra)
C++删除迭代器两种方法对比(list.erase(it++)和it=list.erase(it))
网友评论