描述:https://www.luogu.com.cn/problem/P2014
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择 M 门课程学习，问他能获得的最大学分是多少？
#include <bits/stdc++.h> using namespace std; int n,m; struct edge{ int nxt,to; }d[1009]; int rt,head[1009],tot,val[1009],dp[1009][1009],cnt=1; void add(int u,int v){ d[cnt].nxt=head[u],d[cnt].to=v,head[u]=cnt++; } //定义dp[u][t]为以u为根的子树选t门课的最大收益 void dfs(int u,int t) { if(t<=0) return; for(int i=head[u];i;i=d[i].nxt) { int v=d[i].to; for(int k=0;k<t;k++)//u能选t门课,那么子树最多到t-1 dp[v][k]=dp[u][k]+val[v];//先用根更新子树 dfs(v,t-1); for(int k=1;k<=t;k++)//再更新自己 dp[u][k]=max(dp[u][k],dp[v][k-1]); } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { int x; cin>>x>>val[i]; if(x) add(x,i); else add(0,i); } dfs(0,m);//0是根节点 cout<<dp[0][m];//选m门课程 }
原文：https://www.cnblogs.com/iss-ue/p/12526874.html