[CODEVS1378]选课（树形dp）

题目描述

传送门

题解

f[i][j]表示以i为根的子树选j个的最大值。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int max_n=305;
const int max_e=max_n*2;
int n,m,x,w[max_n],f[max_n][max_n];
int tot,point[max_n],next[max_e],v[max_e];
inline void add(int x,int y){++tot;next[tot]=point[x];point[x]=tot;v[tot]=y;}
inline void dp(int x){
for (int i=point[x];i;i=next[i]){
dp(v[i]);
for (int j=m;j>=1;--j)
for (int k=1; k<=j; k++)
f[x][j]=max(f[x][j],f[x][j-k]+f[v[i]][k]);
}
if (x) for (int i=m; i>=1; i--) f[x][i]=f[x][i-1]+w[x];
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%d%d",&x,&w[i]),add(x,i);
dp(0);
printf("%dn",f[0][m]);
}

总结

注意循环顺序，倒序循环保证更新的都是上一个状态。

最后

以上就是安静大米为你收集整理的[CODEVS1378]选课（树形dp）的全部内容，希望文章能够帮你解决[CODEVS1378]选课（树形dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。