POJ2486 Apple Tree 树上背包

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述POJ2486 Apple Tree 树上背包相关的知识，希望能为你提供帮助。
一句话题意：一棵树，一共n个点，每个点上有一个权值，求从1出发，走k步，最多能遍历到的权值。可以往回走。
第一（二）道树上背包题，先是看了dalao的题解，改了一点就过样例了。然而....TLE？？？改了挺久发现由于多组数据且没有“0 0”的输入，如果不在读入的时候加“~”或“EOF”就会死循环，从而导致TLE。
状态设计：设f[i][j][0/1]为以i为根的子树上，走j步，能得到的最大权值（0/1的表示会在转移方程中描述）考虑：（此处参考dalao@zubizakeli ,侵删qwq）每个节点在最终答案中的类型：1，不经过；2，经过但不返回；3，经过且返回（返回的定义是最终的停止节点不位于该节点的子树中）那么可以进行转移：

文章图片

之后便是一些细节问题：给数组赋初值（从0开始！走0步），更新head数组。
实现还是比较简单的啦。
code

文章图片

1 #include< cstdio> 2 #include< algorithm> 3 #include< cstring> 4 5 using namespace std; 6 7 int n,k,tot; 8 int w[300],head[300]; 9 int f[300][200][3]; 10 struct node{ 11int to,next,val; 12 }edge[300]; 13 14 void add(int x,int y) 15 { 16edge[++tot].to=y; 17edge[tot].next=head[x]; 18head[x]=tot; 19 } 20 21 void read(int & x) 22 { 23x=0; 24char ch=getchar(); 25bool flag=false; 26while(ch< \'0\'||ch> \'9\') flag|=(ch==\'-\'),ch=getchar(); 27while(ch> =\'0\'& & ch< =\'9\') x=(x< < 3)+(x< < 1)+(ch^48),ch=getchar(); 28x=flag ? -x : x; 29 } 30 31 void TreeDp(int u,int fa) 32 { 33for(int i=0; i< =k; i++) f[u][i][1]=w[u],f[u][i][0]=w[u]; 34for(int i=head[u]; i; i=edge[i].next) 35{ 36int v=edge[i].to; 37if(v==fa) continue; 38TreeDp(v,u); 39for(int kk=k; kk> =0; kk--) 40for(int j=0; j< =kk; j++) 41{ 42if(kk> =j+2) f[u][kk][0]=max(f[u][kk][0],f[v][j][0]+f[u][kk-j-2][0]); 43if(kk> =j+2) f[u][kk][1]=max(f[u][kk][1],f[v][j][0]+f[u][kk-j-2][1]); 44if(kk> =j+1) f[u][kk][1]=max(f[u][kk][1],f[v][j][1]+f[u][kk-j-1][0]); 45} 46} 47 } 48 49 void init() 50 { 51memset(f,0,sizeof(f)); 52memset(head,0,sizeof(head)); 53tot=0; 54 } 55 56 int main() 57 { 58while(scanf("%d%d",& n,& k)!=EOF) 59{ 60for(int i=1; i< =n; i++) read(w[i]); 61for(int i=1; i< =n-1; i++) 62{ 63int x=0,y=0; 64read(x),read(y); 65add(x,y),add(y,x); 66} 67TreeDp(1,-1); 68printf("%d\\n",max(f[1][k][0],f[1][k][1])); 69init(); 70} 71return 0; 72 }

View Code【POJ2486 Apple Tree 树上背包】小结：分类讨论常常也是解题重要的突破口呐。