首页 > 代码库 > 【P1303】苹果二叉树
【P1303】苹果二叉树
树归入门题
原题：
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树：
2 5
\ /
3 4
\ /
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
1<=Q<= N,1<N<=100
每根树枝上的苹果不超过30000个。
核心思想是用f[x][y]表示以x为根的子树保留y条根的最大值
每次枚举i，f[x][y]=max(f[x][y],f[lchild][i]+f[rchild][y-i-1])，如果f[lchild][i]==0或f[rchild][y-i-1]==0，进去递归，求出f[lchild][i]或f[rchild][y-i-1]再更新
当size==1或y==0时要特判
刚开始写的时候写成先分别把lchild和rchild从0-size[lchild]或size[rchild]的最优值求出来，在枚举i更新x的从0-size[x]的最优值，不过这么做好想错了，看了oy学长的程序才改过来
不知道像上面这么写↑能不能写对，还需要做更多的题总结
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int read(){int z=0,mark=1; char ch=getchar(); 8 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1; ch=getchar();} 9 while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘; ch=getchar();}10 return z*mark;11 }12 struct ddd{int next,y,value;}e[210];int LINK[110],ltop=0;13 inline void insert(int x,int y,int z){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;e[ltop].value=http://www.mamicode.com/z;}14 struct dcd{int lchild,rchild,value,size;}tree[210];15 int n,m;16 bool visited[110];17 int f[110][110];18 void get_tree(int x,int y){19 visited[x]=true;20 tree[x].value=http://www.mamicode.com/y;21 for(int i=LINK[x];i;i=e[i].next)if(!visited[e[i].y]){22 if(!tree[x].lchild) tree[x].lchild=e[i].y;23 else tree[x].rchild=e[i].y;24 get_tree(e[i].y,e[i].value);25 }26 tree[x].size=tree[tree[x].lchild].size+tree[tree[x].rchild].size+1;27 }28 void tree_DP(int x,int y){29 if(y==0) f[x][y]=0;30 else if(!tree[x].lchild && !tree[x].rchild) f[x][y]=tree[x].value;31 else{32 for(int i=0;i<y;i++){33 if(f[tree[x].lchild][i]==0) tree_DP(tree[x].lchild,i);34 if(f[tree[x].rchild][y-i-1]==0) tree_DP(tree[x].rchild,y-i-1);35 f[x][y]=max(f[x][y],f[tree[x].lchild][i]+f[tree[x].rchild][y-i-1]);36 }37 f[x][y]+=tree[x].value;38 }39 }40 int main(){//freopen("ddd.in","r",stdin);41 memset(visited,0,sizeof(visited));42 memset(tree,0,sizeof(tree));43 memset(f,0,sizeof(f));44 cin>>n>>m;45 int _left,_right,_value;46 for(int i=1;i<n;i++){47 _left=read(); _right=read(); _value=http://www.mamicode.com/read();48 insert(_left,_right,_value); insert(_right,_left,_value);49 }50 get_tree(1,0);51 tree_DP(1,m+1);52 cout<<f[1][m+1]<<endl;53 return 0;54 }
【P1303】苹果二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。