https://www.luogu.com.cn/problem/P2014
在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有 N 门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择 M 门课程学习,问他能获得的最大学分是多少?
说是题解实际是留个备份方便以后自己找。
https://www.luogu.com.cn/blog/P6174/solution-p2014
这位的题解是我见过最清新的$O(NM)$的树形背包题解了。
#include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=305; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct node{ int to,nxt; }e[N]; int n,m,cnt,head[N]; inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt; } int w[N],f[N][N],idx[N],sz[N],tot; void dfs(int u){ sz[u]=1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; dfs(v);sz[u]+=sz[v]; } idx[++tot]=u; } int main(){ int n=read(),m=read()+1; for(int i=1;i<=n;i++){ int u=read(),v=i; add(u,v);w[v]=read(); } dfs(0); for(int i=1;i<=tot;i++){ for(int j=1;j<=m;j++){ f[i][j]=max(f[i-1][j-1]+w[idx[i]],f[i-sz[idx[i]]][j]); } } printf("%d\n",f[tot][m]); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++