BYR Achieve · 镜像论坛

发信人: magicpig (palatable), 信区: ACMICPC 标题: 树型dp小议发信站: 逸仙时空 Yat-sen Channel (Tue May 10 21:20:44 2005), 转信上次出了一题Apple Tree, 很多朋友发信过来讨论。鉴于大家对树型dp的兴趣，鄙人虽然表达能力有限，也尽力水一下，写出对树型dp的一点浅见。有错之处，希望大家指出。树型dp，就是一棵树上做dp。由于树的结构比较简单，单路连通，具有很优的状态转移结构。题目的一般出法是父节点状态由子树状态决定.所以，我们只要DFS一次就可以完成了。(当然，还有其他很多考察方法）状态的转移是比较繁琐的事情。在求出子树状态的情况下，得出父节点状态。节点状态也许很多(Apple Tree就是一个例子)。所以，处理好状态的转移就是搞掂树型dp的关键。除此，树的存储一般用邻接表，当然规模小的话可以用邻接矩阵。邻接表的实现方法很多，我喜欢用stl的vector,偶尔用用静态链表(运行时间少一点，让自己开心一下:) ) （精华区7－3有简要的介绍和一些题目推荐) 我们来看两道题目 ///////////////////////////////////////////////////////////////////// //Apple Tree //数组二维go，bk //go[t][i]代表节点t的所有子树上走i步不返回,取得的最大苹果数 //bk[t][i]代表节点t的所有子树上走i步并返回,取得的最大苹果数 //求节点为x，实行不断合并子树求最优值 //当前合并到了q棵子树： //go[x][i]就是这q棵子树上走i步不返回的最优值 //bk[x][i]就是这q棵子树上走i步并返回的最优值 //合并第q+1棵子树(不妨设第q+1棵子树的根为y)的时候，有 //go[x][i] = max( bk[x][j]+go[y][i-j], bk[y][j],go[x][i-j] ), j=0.....i //bk[x][i] = max( bk[x][j]+bk[y][i-j] ) j=0,.....i; //////////////////////////////////////////////////////////////////////////// / //用了vector ＃i nclude <stdio.h> ＃i nclude <string.h> ＃i nclude <vector> #define MAX 101 using namespace std; int apple[MAX], bk[MAX][MAX*2], go[MAX][MAX*2], n, k, temp1[MAX*2], temp2[MAX*2]; vector<int> nxt[MAX]; int max(int x, int y){return x>y?x:y;} void dp(int x, int y){ int i, j; memset(temp1,0,sizeof(temp1)); memset(temp2,0,sizeof(temp2)); for(i=0;i<=k;i++)for(j=0;j<=i;j++) temp1[i] = max(temp1[i], max(bk[x][j]+go[y][i-j], bk[y][j]+go[x][i-j]) ); for(i=0;i<=k;i++)for(j=0;j<=i;j++) temp2[i] = max(temp2[i], bk[x][j]+bk[y][i-j] ); for(i=0;i<=k;i++) bk[x][i] = temp2[i], go[x][i] = temp1[i]; return ; } void search(int x, int f){ int i, j, l; for(i=0;i<nxt[x].size();i++)if( (j=nxt[x][i]) != f ){ search(j,x); for(l=k;l>=2;l--)bk[j][l] = bk[j][l-2] + apple[j]; bk[j][0] = bk[j][1] = go[j][0] = 0; for(l=k;l>=1;l--)go[j][l] = go[j][l-1] + apple[j]; dp(x,j); } return ; } int main(){ // freopen("Apple.in","r",stdin); // freopen("Apple.out","w",stdout); int i, a, b; while( scanf("%d%d",&n,&k)!=EOF ){ for(i=0;i<n;i++)nxt[i].clear(); memset(bk,0,sizeof(bk)); memset(go,0,sizeof(go)); for(i=0;i<n;i++)scanf("%d",apple+i); for(i=1;i<n;i++){ scanf("%d%d",&a,&b); a--,b--; nxt[a].push_back(b); nxt[b].push_back(a); } search(0,0); printf("%d\n",go[0][k] + apple[0]); } return 0; } ///////////////////////////////////////////////////////////////// //pku 1155 //http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1155 //对于A节点 //数组a， b //a[i]代表A的前k棵子树上取i个叶子，可以赚取的最大费用 //b[i]代表A的第k+1棵子取i个叶子，可以赚取的最大费用 //假设前k棵子树有k1个叶子，第k+1棵子树有k2个叶子 //现在要求的是前k＋1棵子树，取k个叶子(0<=k<=k1+k2)的数组c[k] //显然，就是两重循环 //for(k=0;k<=k1+k2;k++)for(i=0;i<=k1;i++) c[k] = max(c[k],a[i]+b[k-i]); //当然，要加入越界检查： /////////////////////////////////////////////////////////////////////// //以下代码用了静态链表＃i nclude <stdio.h> ＃i nclude <vector> using namespace std; #define MAX 3001 struct pp{ int idx, cost, pre; void set(int i, int c, int p){ idx = i, cost = c, pre = p; } }tree[MAX]; int pay[MAX], memory[MAX], temp[MAX], head[MAX]; inline int max(int x, int y){return x>y?x:y;} int search(int x, int s, int w){ int pre, add, j, a, start; pre=memory[s]=0; if(head[x]==-1){ memory[s+1] = pay[x] - w; return 1; } while(head[x]+1){ add = search(tree[head[x]].idx, s+pre+1, tree[head[x]].cost); for(j=0;j<=add+pre;j++){ temp[j] = -1000000; start = max(0,j-add); for(a=start;a<=pre&&a<=j;a++) temp[j] = max(memory[s+a]+memory[s+pre+1+j-a], temp[j]); } pre+=add; for(j=0;j<=pre;j++)memory[s+j] = temp[j]; head[x] = tree[head[x]].pre; } for(j=1;j<=pre;j++) memory[s+j] -= w; return pre; } int main(){ int n, m, i,k,a,b, now; memset(head,255,sizeof(head)); while(scanf("%d%d",&n,&m)!=EOF){ for(i=1,now=0;i<=n-m;i++){ scanf("%d",&k); while(k--){ scanf("%d%d",&a,&b); tree[now].set(a,b,head[i]); head[i] = now++; } } for(;i<=n;i++) scanf("%d",pay+i); search(1,0,0); while(memory[m]<0)m--; printf("%d\n",m); } return 0; }

[转帖] POJ Apple Tree (tree dp)