hdu1561 The more, The Better 树形DP+分组背包

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1561

思路：

典型的树形背包题目：

定义dp[i][j]表示以i为根节点，攻打j个城堡的获得的财宝的最优值，那么dp[i][j]=max(dp[i][j],dp[son][k]+dp[i][j-k]) 其中son为i的儿子

然后从叶子节点往上进行背包即可

刚接触的同学会有疑问：就是不知道怎样将题目中的数据建为一个树，其实很简单，只要把0作为根结点即可 0节点的value初始化为0

然后dp[0][m+1]即为求得的答案，是不是很简单啊。。。。

注意初始化。

代码如下：

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define MAX 210

 int dp[MAX][MAX];

 vector<int>v[MAX];

 int vis[MAX];

 int m,n;

 void init()

 {

  memset(dp,-,sizeof(dp));

  memset(vis,,sizeof(vis));

  for(int i=;i<MAX;i++) v[i].clear();

 }

 void dfs(int root)

 {

         vis[root]=;

        for(int i=;i<v[root].size();i++)

        {

           if(vis[v[root][i]]) continue;

           int son=v[root][i];

           dfs(son);

           for(int i=m;i>=;i--)

             for(int j=;j<i;j++)

                     if(dp[root][i-j]!=-&&dp[son][j]!=-)

                         dp[root][i]=max(dp[root][i],dp[son][j]+dp[root][i-j]);

        }

 }

 int main()

 {

    while(scanf("%d%d",&n,&m)!=EOF)

    {

       init();

       if(n==&&m==) break;

       for(int i=;i<=n;i++)

       {

          int a,b;

          scanf("%d%d",&a,&b);

          v[a].push_back(i);

          dp[i][]=b;

          dp[i][]=;

       }

       m++;

       dp[][]=;

       dp[][]=;

       dfs();

       cout<<dp[][m]<<endl;

    }

    return ;

 }

巴特西

hdu1561 The more, The Better 树形DP+分组背包

最新文章

热门文章