posts - 74, comments - 33, trackbacks - 0

以前做树状dp的时候就知道Apple Tree,可是感觉上有点困难就一直搁浅，昨天刷浙大月赛的Tree of Tree骤然想明白了这个dp过程中的背包。
明显Apple Tree要难一些。。。。今天停了一天的电没有时间调试代码，刚才终于AC，貌似时间上还可以

5100258(2)

xujiaming

568K

63MS

C++

1315B

2009-05-05 20:39:29

建议先做一做Tree of Tree,其实两道题的代码相似，我的dp函数

void DFS(int x){

int i,j;

dp[x][1]=DP[x][1]=arr[x];

for(i=0;i<v[x].size();i++){

int t=v[x][i];

if(!mark[t]){

mark[t]=true;DFS(t);

for(j=1;j<=k;j++){

TMP[j]=DP[x][j];

tmp[j]=dp[x][j];

}

for(j=1;j<=k;j++)

for(int l=1;l<=k;l++){

if(dp[t][j]!=-1&&TMP[l]!=-1)dp[x][l+j]=getmax(dp[x][l+j],dp[t][j]+TMP[l]);

if(DP[t][j]!=-1&&TMP[l]!=-1)DP[x][l+j+1]=getmax(DP[x][l+j+1],DP[t][j]+TMP[l]);

if(DP[t][j]!=-1&&tmp[l]!=-1)dp[x][l+j+1]=getmax(dp[x][l+j+1],DP[t][j]+tmp[l]);

}

return ;

}

配合代码解释一下：
1.按给定的树取一个节点做为root开始DFS，而这个节点的每一个子树的dp状态完全可以根据背包的思想转移到这个这个root跟新的时候用tmp存储一下状态，防止此次根据子树跟新影响现在的dp状态，而dp过程中要有两种dp状态一种是可以回到root，一种是不可以回到root，即（DP，dp）

posted on 2009-05-05 20:50 KNIGHT 阅读(173) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2009年6月

日

一

二

三

四

五

六

常用链接

留言簿(8)

随笔档案

文章档案

2009年3月 (1)

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

最新评论

阅读排行榜

评论排行榜