Apple Tree POJ - 2486

2018-06-17 21:36:04来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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])。

曾经错误:

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 {
 7     int 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 {
15     int j,kk=f1[u],p,v;
16     vis[u]=true;
17     for(j=0;j<=k;j++)
18         ans[u][j][0]=ans[u][j][1]=a[u];
19     while(kk!=0)
20     {
21         v=edge[kk].to;
22         if(!vis[v])
23         {
24             dfs(v);
25             for(j=k;j>=0;j--)
26             {
27                 for(p=1;p<=j;p++)
28                     ans[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]));
29                 for(p=2;p<=j;p++)
30                     ans[u][j][1]=max(ans[u][j][1],ans[u][j-p][1]+ans[v][p-2][1]);
31             }
32         }
33         kk=edge[kk].next;
34     }
35 }
36 int main()
37 {
38     int i,ta,tb;
39     while(scanf("%d%d",&n,&k)==2)
40     {
41         ne=0;
42         memset(ans,0,sizeof(ans));
43         memset(vis,0,sizeof(vis));
44         memset(f1,0,sizeof(f1));
45         for(i=1;i<=n;i++)
46             scanf("%d",&a[i]);
47         for(i=1;i<n;i++)
48         {
49             scanf("%d%d",&ta,&tb);
50             edge[++ne].to=tb;
51             edge[ne].next=f1[ta];
52             f1[ta]=ne;
53             edge[++ne].to=ta;
54             edge[ne].next=f1[tb];
55             f1[tb]=ne;
56         }
57         dfs(1);
58         printf("%d\n",max(ans[1][k][0],ans[1][k][1]));
59     }
60     return 0;
61 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:2017.11.10 重读C++ Primer

下一篇:【DTOJ】2703:两个数的余数和商