73: luogu 2014 树形dp
$des$
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
$des$
建出完整的树后 dp
#include <bits/stdc++.h> using namespace std; #define Rep(i, a, b) for(int i = a; i <= b; i ++) const int N = 305; int fa[N]; vector <int> G[N]; int n, q; int w[N]; int f[N][N]; void Dfs(int u) { int S = G[u].size(); Rep(i, 0, S - 1) { int v = G[u][i]; Dfs(v); for(int j = q + 1; j >= 1; j --) { for(int k = 0; k < j; k ++) { f[u][j] = max(f[u][j], f[v][k] + f[u][j - k]); } } } } int main() { cin >> n >> q; Rep(i, 1, n) { cin >> fa[i] >> w[i]; f[i][1] = w[i]; G[fa[i]].push_back(i); } Dfs(0); cout << f[0][q + 1]; return 0; }优质内容筛选与推荐>>
1、bzoj2427 [HAOI2010]软件安装
2、sql中连接两个不同的数据库(A在同一个服务器,B不在一个服务器)
3、电梯演说模版练习
4、Greenplum——升级的分布式PostgresSQL
5、AAuto如何设置combobox