前置技能 : 树形DP
如果做过选课的话,想必各位一看到就知道这是一道树形DP的题目
0x02 题目
题目中要求我们在以收入$\geq 0$的前提下,支持尽可能多的叶子节点
因此我们可以这么定义一个类似背包状态转移方程
$$
f(now,i+j)=max(f(now,i+j),f(son,j)+f(now,i)-val)
$$
这不就是背包吗<(=°д)ノ
边界条件
$$
f(i,j)=-INF(0\leq i \leq N,0 \leq j \leq M)
$$
设为$-INF$是为了防止无法转移
看起来很显然是吧
让我们来看看代码:
0x03 代码
#include <cstdio>
#include <cstring>
const int N=3100;
inline int Max(int a,int b){return a>b?a:b;}
int _case;
int ans,v,w,n,m,son[N];
int f[N][N];
// edge start
struct edge{
int to,next,val;
}e[N];
int ehead[N],ecnt;
inline void add_edge(int now,int to,int val){
ecnt++;
e[ecnt].to=to;
e[ecnt].val=val;
e[ecnt].next=ehead[now];
ehead[now]=ecnt;
}
// edge end
// dfs start
void dfs(int now){
if(now>n-m){// 只有用户才会算到叶子节点中
son[now]=1;
return ;
}
f[now][0]=0;
for(int u=ehead[now];u;u=e[u].next){
dfs(e[u].to);
for(int i=son[now];i>=0;i--){
for(int j=1;j<=son[e[u].to];j++){// 注意循环顺序,不这么循环会重复计算一些东西
f[now][i+j]=Max(f[now][i+j],f[now][i]+f[e[u].to][j]-e[u].val);
}
}
son[now]+=son[e[u].to];
}
}
// dfs end
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n-m;i++){
scanf("%d",&_case);
while(_case--){
scanf("%d%d",&v,&w);
add_edge(i,v,w);
}
}
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=m;i++) scanf("%d",&f[n-m+i][1]);
dfs(1);
for(int i=1;i<=m;i++){
if(f[1][i]>=0) ans=i;
}
printf("%d",ans);
}