锐客网

  1. 首页 > 睿知 > it技术 > >

Apple Tree POJ - 2486

IT知识appletree

最是人间留不住，朱颜辞镜花辞树。这篇文章主要讲述Apple Tree POJ - 2486相关的知识，希望能为你提供帮助。
Apple Tree POJ - 2486
题目大意：一棵点带权有根树，根节点为1。从根节点出发，走k步，求能收集的最大权值和。
树形dp。复杂度可能是O(玄学)，不会超过$O(nk^2)$。（反正这题不卡这个，考思想）参考
ans[i][j][0]表示i点以下共走j步，不回来，可能收集到最大的权值
ans[i][j][1]表示i点以下共走j步，回来，可能收集到最大的权值
比较复杂的是，每个节点（以下称当前节点）从其子节点转移的时候，需要用一个背包：
t[i][j][0]表示当前节点的前i个子节点共走j步，不回来
t[i][j][1]表示当前节点的前i个子节点共走j步，回来
对于t[i][j][0]，要么是当前节点的前i-1个子节点共走j步（包括去和回来前面的子节点所用步数），在之前就不回来；
要么是前i-1个子节点共走j-p步（包括去和回来前面的子节点所用步数），当前节点走到第i个子节点用1步，第i个子节点向下走p-1步，不回来；
要么是花一步走到第i个子节点，在第i个子节点往下走p-2步，再花一步走回当前节点，再在前i-1个子节点中走j-p步（包括去和回来前面的子节点所用步数）并且不回来。
因此t[i][j][0]=max(t[i-1][j][0],max{t[i-1][j-p][1]+ans[nowson][p-1][0]},max{t[i-1][j-p][0]+ans[nowson][p-2][1]})
对于t[i][j][1]，要么是前i-1个子节点共走j-p步（包括去和回来前面的子节点所用步数），走到第i个子节点花1步，第i个子节点向下走用p-2步并回来，从第i个子节点回来花一步；要么是前i-1个子节点共走j步（包括去和回来前面的子节点所用步数），回来。
因此t[i][j][1]=max(t[i-1][j][1],max{t[i-1][j-p][1]+ans[nowson][p-2][1]})
当然实际求解的时候并不需要每个节点开一个t数组，只需要在ans数组上直接做就行了。就是先对t数组求解过程用滚动数组优化，那么只需要两维t[j][0/1]。这时只需要把ans[当前节点]的数组当做t去做就行了。另外，求解t数组的边界要注意一下。另外，t数组再求解前就全部初始化成当前节点权值就行了。
最终答案很显然：max(ans[1][k][0],ans[1][k][1])。
曾经错误：
【Apple Tree POJ - 2486】naive的转移方程：
t[i][j][0]=max(t[i-1][j][0],t[i-1][j-p][0],t[i-1][j-p][1]+ans[son][p][0])
t[i][j][1]=max(t[i-1][j][1],t[i-1][j-p][1]+ans[son][p][1])
事实上，这道题转移t[i][j][0]的第3种（标红的）情况很容易遗漏。另外，很容易忽略走去与走回子节点花费的1或2步。

1 #include< cstdio> 2 #include< cstring> 3 #include< algorithm> 4 using namespace std; 5 struct Edge 6 { 7int to,next; 8 }edge[210]; 9 int ne,ans[110][210][2],f1[110]; 10 int a[110]; 11 int n,k; 12 bool vis[110]; 13 void dfs(int u) 14 { 15int j,kk=f1[u],p,v; 16vis[u]=true; 17for(j=0; j< =k; j++) 18ans[u][j][0]=ans[u][j][1]=a[u]; 19while(kk!=0) 20{ 21v=edge[kk].to; 22if(!vis[v]) 23{ 24dfs(v); 25for(j=k; j> =0; j--) 26{ 27for(p=1; p< =j; p++) 28ans[u][j][0]=max(ans[u][j][0],max(ans[u][j-p][0]+ans[v][p-2][1],ans[u][j-p][1]+ans[v][p-1][0])); 29for(p=2; p< =j; p++) 30ans[u][j][1]=max(ans[u][j][1],ans[u][j-p][1]+ans[v][p-2][1]); 31} 32} 33kk=edge[kk].next; 34} 35 } 36 int main() 37 { 38int i,ta,tb; 39while(scanf("%d%d",& n,& k)==2) 40{ 41ne=0; 42memset(ans,0,sizeof(ans)); 43memset(vis,0,sizeof(vis)); 44memset(f1,0,sizeof(f1)); 45for(i=1; i< =n; i++) 46scanf("%d",& a[i]); 47for(i=1; i< n; i++) 48{ 49scanf("%d%d",& ta,& tb); 50edge[++ne].to=tb; 51edge[ne].next=f1[ta]; 52f1[ta]=ne; 53edge[++ne].to=ta; 54edge[ne].next=f1[tb]; 55f1[tb]=ne; 56} 57dfs(1); 58printf("%d\\n",max(ans[1][k][0],ans[1][k][1])); 59} 60return 0; 61 }


    推荐阅读


    上一篇：B.欢迎来怼——博客园安卓app（测评人（阚博文））

    下一篇：C .Thunder——爱阅app（测评人（方铭））