Tyvj 1051 选课 树形dp

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N =310;
int val[N];
vector<int>g[N];
int dp[N][N];
void dfs(int
rt,int m){
if(m==0) {
return;
}
for(int h=0;h<g[rt].size();h++){
int u=g[rt][h];
for(int i=0;i<=m;i++){
dp[u][i]=dp[rt][i];
}
dfs(u,m-1);
for(int i=m;i>=1;i--){
dp[rt][i]=max(dp[rt][i],dp[u][i-1]+val[u]);
}
}
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<=n;i++){
g[i].clear();
}
int x;
val[0]=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&val[i]);
if(x==0) g[0].push_back(i);
else g[x].push_back(i);
}
memset(dp,0,sizeof(dp));
dfs(0,m);
printf("%dn",dp[0][m]);
}
return 0;
}

最后

以上就是阳光绿草为你收集整理的Tyvj 1051 选课 树形dp的全部内容，希望文章能够帮你解决Tyvj 1051 选课 树形dp所遇到的程序开发问题。

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