[CTSC1997]选课【背包类树形dp】

159 阅读 0 评论 105 点赞

我是靠谱客的博主俭朴小鸭子，这篇文章主要介绍[CTSC1997]选课【背包类树形dp】，现在分享给大家，希望可以做个参考。

[CTSC1997]选课

【树形 $DP$ 】
一眼算法题（区分差分约束与拓扑排序）
注意到有些功课可能没有前置功课，于是把所有没有前置功课的点都与 $0$ 连边，然后进行树形 $DP$ 。注意到 $0$ 这个点要强制被选，那么最后选课个数就是 $m+1$ 。注意这道题属于 $01$ 背包类树形 $DP$ ，以节点编号作为 $DP$ 阶段，像线性 $DP$ 一样，把当前背包的体积作为第二维状态，在状态转移的时候实际上就是一个分组背包问题。

复制代码

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
#include <bits/stdc++.h>
using namespace std;
const int N=350;
int n,m,x,y,ans,f[N][N],sz[N],fir[N<<1],nxt[N<<1],to[N<<1],tot;
inline int read(){
int cnt=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){cnt=(cnt<<1)+(cnt<<3)+(c^48);c=getchar();}
return cnt*f;
}
inline void add(int x,int y){nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;}
void dfs(int u){
for(int i=fir[u];i;i=nxt[i]){
int v=to[i];
dfs(v);sz[u]+=sz[v]+1;
for(int j=max(m+1,sz[u]);j;--j){//倒序循环正确处理组内体积为0的物品
for(int k=0;k<=j-1;++k){
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
}
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i) {x=read(),f[i][1]=read(),add(x,i);}
dfs(0);
printf("%d",f[0][m+1]);
return 0;
}