随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=2196
向下搜一遍,向上搜一遍
http://acm.hdu.edu.cn/showproblem.php?pid=1561
对每一个节点进行一次背包,好题啊,两个DP树形和背包结合的
http://acm.hdu.edu.cn/showproblem.php?pid=1011
这道是当年省赛的压轴题,但是感觉和上一道差不多,一样的难度,唯一不同的就是这个是无向图(我由于思维惯性拿来当单向图作,纠结了好久。。。)
树形+背包+临街表

下边是从天涯空间里找出来的练习
http://acm.pku.edu.cn/JudgeOnline/problem?id=3345
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201
http://acm.pku.edu.cn/JudgeOnline/problem?id=3107
http://acm.pku.edu.cn/JudgeOnline/problem?id=1655
http://acm.pku.edu.cn/JudgeOnline/problem?id=2378
http://acm.pku.edu.cn/JudgeOnline/problem?id=3140
http://acm.hdu.edu.cn/showproblem.php?pid=2242
http://acm.timus.ru/problem.aspx?space=1&num=1018
http://acm.pku.edu.cn/JudgeOnline/problem?id=1947
http://acm.pku.edu.cn/JudgeOnline/problem?id=2057
http://acm.pku.edu.cn/JudgeOnline/problem?id=2486
http://acm.pku.edu.cn/JudgeOnline/problem?id=1848
http://acm.pku.edu.cn/JudgeOnline/problem?id=2152



http://acm.hdu.edu.cn/showproblem.php?pid=1520
(第一个树形DP,附代码)
最最简单的树形DP
还学习了父子兄弟结构,爽

#include "stdio.h"

struct Tree{
    
int father;
    
int child;
    
int brother;
    
int TakeParty;
    
int Not;
    
int Max() {
        
return TakeParty > Not ? TakeParty : Not;
    }
    
void init() {
        father 
= child = brother = Not = 0;
    }
}tree[
6001];

void dfs(int idx ) {
    
int child;
    child 
= tree[idx].child;
    
while(child) {
        dfs(child);
        tree[idx].TakeParty 
+= tree[child].Not;
        tree[idx].Not 
+= tree[child].Max();
        child 
= tree[child].brother;
    }
}

int main() {
    
int n,i,a,b;
    
while(scanf("%d",&n) == 1) {
        
for(i =1 ; i <= n ; i ++) {
            scanf(
"%d",&tree[i].TakeParty);
            tree[i].init();
        }
        
while(scanf("%d%d",&a,&b),a+b) {
            tree[a].father 
= b;
            tree[a].brother 
= tree[b].child;
            tree[b].child 
= a;
        }
        
for(i = 1 ; i <= n ; i ++) {
            
if(!tree[i].father) {
                dfs(i);
                printf(
"%d\n",tree[i].Max());
                
break;
            }
        }
    }
    
return 0;
}

posted on 2009-05-11 20:39 shǎ崽 阅读(6051) 评论(4)  编辑 收藏 引用

评论:
# re: 树形DP 2009-05-12 17:16 | zjfc3
左儿子右兄弟法??不错  回复  更多评论
  
# re: 树形DP 2010-08-08 11:36 | TT
LZ有没hdu 1561的代码 学习下  回复  更多评论
  
# re: 树形DP 2013-04-07 21:29 | 随心小亚
@TT
1561 的代码我有,但是不知道如何判断-1的情况:
var
n,m,i:longint;
fa,w:array [1..200] of longint;
f:array [0..200,0..200] of longint;
procedure dfs(h,s:longint);
var
i,j:longint;
begin
if s<=0 then exit;
for i:=1 to n do
if fa[i]=h then begin
for j:=0 to s-1{cost[child]} do f[i,j]:=f[h,j];
dfs(i,s-1{cost[child]});
for j:=1{cost[child]} to s do
if f[h,j]<f[i,j-1]+w[i] then
f[h,j]:=f[i,j-1]+w[i];
end;
end;
begin
repeat
readln(n,m);
if not ((n=0)and(m=0)) then begin
for i:=1 to n do readln(fa[i],w[i]);
dfs(0,m-0);
writeln(f[0,m-0]);
end;
until (n=0)and(m=0);
end.  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理