树型dp小议 zz
发信人: Perl (Perl), 信区: ACMICPC
标
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
: 树型dp小议 zz
发信站: 荔园晨风BBS站 (Fri Jul 14 21:28:40 2006), 站内
发信人: 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
#include
#include
#include
#define MAX 101
using namespace std;
int apple[MAX], bk[MAX][MAX*2], go[MAX][MAX*2], n, k, temp1[MAX*2], temp2[MA
X*2];
vector 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=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
#include
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], t
emp[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;
}
////////////////////////////////////////////////////////////////////////////
///////
--
※ 来源:．逸仙时空 Yat-sen Channel bbs.zsu.edu.cn．[FROM: 192.168.50.170]
※ 修改:．magicpig 于 May 10 23:24:18 修改本文．[FROM: 192.168.50.170]
--
There is more than one way to do it.
※ 来源:?荔园晨风BBS站 bbs.szu.edu.cn?[FROM: 218.17.77.137]
浙公网安备 33021202002483