http://acm.timus.ru/problem.aspx?space=1num=1018Binary Apple Tree

本文主要是介绍http://acm.timus.ru/problem.aspx?space=1num=1018Binary Apple Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一棵树，树上有很多苹果，现在要求你砍去一些树枝，问你砍去树枝后最多可以保留多少苹果，树形dp入门题

dp[i][j]表示以i为根节点保留j个树枝最多可以保留的苹果数。可得动态转移方程dp[i][j]=max(dp[i][j],dp[la][i]+dp[ra][j-i+1]);

AC代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct node{
int lc;
int rc;
int s;
}Node;
Node tree[205];
int dp[105][105],apple[105][105];
bool visit[105];
int n;
void init()
{
memset(dp,-1,sizeof(dp));
memset(tree,0,sizeof(tree));
memset(apple,-1,sizeof(apple));
}
void Built_tree(int root){
visit[root]=true;
for(int i=1;i<=n;++i)
if(!visit[i]&&apple[root][i]!=-1){
if(tree[root].lc==0)  tree[root].lc=i;
else  tree[root].rc=i;
tree[i].s=apple[root][i];
Built_tree(i);
}
}
int Tree_dp(int p,int k)
{
if(dp[p][k]!=-1) return dp[p][k];
if(p==0||k==0) return  0;
dp[p][k]=0;
for(int i=0;i<=k-1;++i)
{
int l=Tree_dp(tree[p].lc,i);
int r=Tree_dp(tree[p].rc,k-1-i);
dp[p][k]=max(dp[p][k],l+r);
}
dp[p][k]+=tree[p].s;
return dp[p][k];
}
int main()
{
int m;
cin>>n>>m;
init();
for(int i=0;i!=n-1;++i)
{
int a,b,c;
cin>>a>>b>>c;
apple[a][b]=apple[b][a]=c;
}
Built_tree(1);
cout<<Tree_dp(1,m+1)<<endl;
return 0;
}

 

这篇关于http://acm.timus.ru/problem.aspx?space=1num=1018Binary Apple Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---