随笔-68  评论-10  文章-0  trackbacks-0

依赖背包(树形背包)。见代码:

#include<iostream>
#include
<vector>
using namespace std;
int N,M;
int val[205];
int vis[205];
int f[205][205];
int dp[205][205];
vector
<int> tree[205];

int max(int a,int b)
{
    
return a>b?a:b;
}


void dfs(int x)
{
    
int i,j,k;
    vis[x]
=1;
    dp[x][
0]=0;
    f[x][
0]=0;

    
for(i=0;i<tree[x].size();i++)
        
for(j=M;j>=0;j--)
        
{
            
int temp=tree[x][i];
            
if(!vis[temp]) dfs(temp);
            
for(k=0;k<=M;k++)
            
{
                
if(dp[temp][k]!=-1&&j>=k&&f[x][j-k]!=-1)
                    f[x][j]
=max(f[x][j],f[x][j-k]+dp[temp][k]);
            }

        }

    
for(i=1;i<=M+1;i++)
        
if(f[x][i-1]!=-1) dp[x][i]=f[x][i-1]+val[x];
}


int main()
{
    
while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
    
{
        
int i,a,b;
        
for(i=0;i<=N;i++)
            tree[i].clear();
        
for(i=1;i<=N;i++)
        
{
            scanf(
"%d%d",&a,&b);
            tree[a].push_back(i);
            val[i]
=b;
        }


        val[
0]=0;
        memset(vis,
0,sizeof(vis));
        memset(dp,
-1,sizeof(dp));
        memset(f,
-1,sizeof(f));
        dfs(
0);
        printf(
"%d\n",dp[0][M+1]);
    }

    
return 0;
}


posted on 2010-08-05 18:00 wuxu 阅读(959) 评论(4)  编辑 收藏 引用 所属分类: 动态规划

评论:
# re: hdu1561 2010-08-07 22:18 | TT
lz 能问下 为什么在DFS里面进行DP的时候 要判断不等于-1的进行DP 不判断 两个数组都全赋值成0直接做 会有哪里错呢 不是很明白 希望指点  回复  更多评论
  
# re: hdu1561 2010-08-07 22:36 | wuxu
@TT
这道题两数组全赋值为0好像也可以过的, 对于赋值为-1,我是这么理解的:
如果为-1,则说明该状态还未出现,不用考虑,但是如果为0,就不能表达这个意思。  回复  更多评论
  
# re: hdu1561 2010-08-08 10:28 | TT
哦 -1是为了防止多余的无用操作 可以这么理解么 用0可以过 速度慢点 不过我不是很确定是不是这题的测试数据弱的情况导致 用0也对 原理很模糊 初次接触树形DP  回复  更多评论
  
# re: hdu1561 2010-08-08 17:01 | TT
能不能加下我qq 有些问题想向您请教 评论讲不清楚 251673671  回复  更多评论
  

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