HDU 1561 The more, The Better 依赖背包+树形DP
发布时间:2020-05-27 04:05:41 所属栏目:程序设计 来源:互联网
导读:点击打开链接 The more, The Better Time Limit: 6000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4375Accepted Submission(s): 2591 Problem Description ACboy很喜欢
点击打开链接 The more,The BetterTime Limit: 6000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0
5 13
#include<stdio.h> #include<string.h> #include<vector> #define M 207 using namespace std; vector<int>v[M]; int happy[M],vis[M],dp[M][M]; int n,m; void dfs(int x) { vis[x]=1; dp[x][1]=happy[x]; int len=v[x].size(); for(int i=0;i<len;i++) { int u=v[x][i]; if(!vis[u]) dfs(u); for(int j=m+1;j>=1;j--) for(int k=1;k<j;k++) dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[u][k]); } } int main() { while(scanf("%d%d",&n,&m),n|m) { int a,b; memset(dp,sizeof(dp)); memset(vis,sizeof(vis)); for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); v[a].push_back(i); happy[i]=b; } dfs(0); printf("%dn",dp[0][m+1]); } return 0; } (编辑:安卓应用网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |