【题目描述】 在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有$N$门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少?
【输入格式】 第一行有两个整数$N$,$M$用空格隔开。($1 \leq N \leq 300$,$1 \leq M \leq 300$)
接下来的$N$行,第$I+1$行包含两个整数$k_i$和$s_i$,$k_i$表示第$I$门课的直接先修课,$s_i$表示第$I$门课的学分。若$k_i=0$表示没有直接先修课($1 \leq {k_i} \leq N$,$1 \leq {s_i} \leq 20$)。
【输出格式】 只有一行,选$M$门课程的最大得分。
题解
可以看出如果将课程向它的先修课连边 会形成一棵树 其中$0$号节点就是根
显然是一个背包问题。。。外面再套一个树形DP
先令$f[x][i][j]$表示$x$的子树中 枚举到$x$的第$i$个儿子 在$x$的子树中一共选了$j$个节点 的最大学分
从一个儿子的子树里按规则取$k$个节点出来就相当于一个重量为$k$,权值为$f[son][子树大小][k]$的物品 显然你从一个儿子那里只能选择一个这样的物品 你不可能既从这个儿子的子树中选取3个节点 又再选取重复的2个节点 所以实际上就是一个分组背包 一个组就是一个儿子的子树
那么转移方程是$f[x][i][j]=\min_{k=1}^{j-1}(f[x][i-1][j],f[x][i-1][j-k]+f[son[i]][tot][k])$ $son[i]$就是$x$的第$i$个儿子$tot$就当是$son[i]$的子树大小吧
初始状态:$dp[x][0][1] = s_x$其他的都设成$-inf$
根据背包DP的尿性$i$那一维是可以通过倒着枚举来优化掉,降低空间复杂度的(虽然不优化也没事)。。。
时间复杂度大大低于$O(n^3)$
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <bits/stdc++.h> using namespace std ;inline int read () { int x = 0 , f = 1 ; char ch = getchar(); for (; ch > '9' || ch < '0' ; ch = getchar()) if (ch == '-' ) f = -1 ; for (; ch <= '9' && ch >= '0' ; ch = getchar()) x = (x << 1 ) + (x << 3 ) + (ch ^ '0' ); return x * f; } int n, m;int head[305 ], pre[605 ], to[605 ], sz;int a[305 ], f[305 ][305 ];inline void addedge (int u, int v) { pre[++sz] = head[u]; to[sz] = v; head[u] = sz; pre[++sz] = head[v]; to[sz] = u; head[v] = sz; } void dfs (int x, int fa) { f[x][1 ] = a[x]; for (int i = head[x]; i; i = pre[i]) { int y = to[i]; if (y == fa) continue ; dfs(y, x); for (int j = m; j >= 1 ; j--) { for (int k = 0 ; k < j; k++) { f[x][j] = max(f[x][j], f[y][k] + f[x][j-k]); } } } } int main () { n = read(); m = read() + 1 ; for (int i = 1 ; i <= n; i++) { addedge(read(), i); a[i] = read(); } memset (f, -0x3f , sizeof (f)); dfs(0 , 0 ); printf ("%d\n" , f[0 ][m]); return 0 ; }