选课 给定M 门课程，每门课程有一个学分 要从M 门课程中选择N 门课程，使得学分总和最大 其中选择课程必须满足以下条件： 每门课程最多只有一门直接先修课 要选择某门课程，必须先选修它的先修课 M,N=500分析 每门课程最多只有1 门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。 如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。 这样，问题就转化为在一个M 个结点的森林中选取N 个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。样例分析 如图1 ，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了1 棵树，选取结点时，从每个儿子出发进行选取。显然选M=4时，选3 ，2 ，7 ，6 几门课程最优。动态规划 如果我们单纯从树的角度考虑动态规划，设以i 为根结点的树选j 门课程所得到的最大学分为f(i,j), 设虚拟的树根编号为0 ，学分设为0 ，那么，ans=f(0,n+1) 如果树根选择1 门功课，剩下j-1 门功课变成了给他所有儿
