【题目链接】
【算法】
树形DP
f[i][j]表示以i为根的子树中，选了j个叶子节点，所能带来的最大收益
不难发现这就是一个经典的背包问题，不过是在树上做背包罢了
最后，判断f[1][i]是否大于等于0，输出最大的i
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 3010 const int INF = 2e9; int i,j,a,c,k,x,n,m; vector< pair<int,int> > e[MAXN]; int size[MAXN],f[MAXN][MAXN]; inline void dfs(int x) { int i,j,k,y,cost; for (i = 0; i < e[x].size(); i++) { y = e[x][i].first; cost = e[x][i].second; dfs(y); size[x] += size[y]; for (j = size[x]; j >= 1; j--) { for (k = 1; k <= size[y]; k++) { if (j >= k && f[x][j-k] != -INF && f[y][k] != -INF) f[x][j] = max(f[x][j],f[x][j-k]+f[y][k]-cost); } } } } int main() { scanf("%d%d",&n,&m); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { f[i][j] = -INF; } } for (i = 1; i <= n - m; i++) { scanf("%d",&k); for (j = 1; j <= k; j++) { scanf("%d%d",&a,&c); e[i].push_back(make_pair(a,c)); } } for (i = n - m + 1; i <= n; i++) { scanf("%d",&x); size[i] = 1; f[i][1] = x; } dfs(1); for (i = m; i >= 1; i--) { if (f[1][i] >= 0) { printf("%d ",i); break; } } return 0; }