HDU 1561 (树形DP+背包)

我就是我 2021-12-22 10:47 310阅读 0赞

**题目链接**: [http://acm.hdu.edu.cn/showproblem.php?pid=1561][http_acm.hdu.edu.cn_showproblem.php_pid_1561][  
][Link 1]

**题目大意**：从树根开始取点。最多取m个点，问最大价值。

**解题思路**：

cost=1的树形背包。

有个虚根0，取这个虚根也要cost，所以最后的结果是dp\[0\]\[m+1\]。

本题是cost=1的特殊背包问题，在两个for循环上有一个优化。

for(f+1...j....cost)

for(1....k...j-cost)

其中f为当前已经dfs子结点个数。之所以+1，是因为根要预留一个空间。

f+=dfs(t)，dfs(t)返回的是子点t的f+1。

其实可以直接把f+1写成m+1, 不过要多好多次没必要的循环。

#include "cstdio"
    #include "vector"
    #include "cstring"
    using namespace std;
    #define maxn 205
    int n,m,u,dp[maxn][maxn],w[maxn],head[maxn],tol;
    struct Edge
    {
        int to,next;
    }e[maxn];
    void addedge(int u,int v)
    {
        e[tol].to=v;
        e[tol].next=head[u];
        head[u]=tol++;
    }
    int dfs(int root)
    {
        int i=root,cost=1,f=0;
        for(int i=cost;i<=m;i++) dp[root][i]=w[root];
        if(head[root]==-1) return 1;
        for(int a=head[root];a!=-1;a=e[a].next)
        {
            int t=e[a].to;
            f+=dfs(t);
            for(int j=f+1;j>=1;j--)
            {
                for(int k=1;k<=j-cost;k++)
                {
                    dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[t][k]);
                }
            }
        }
        return f+1;
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        while(scanf("%d%d",&n,&m)&&n&&m)
        {
            memset(head,-1,sizeof(head));
            tol=0;
            for(int i=1;i<=n;i++)
            {
                scanf("%d%d",&u,&w[i]);
                addedge(u,i);
            }
            dfs(0);
            printf("%d\n",dp[0][m+1]);
            memset(dp,0,sizeof(dp));
        }
    }

<table> 
 <tbody> 
  <tr> 
   <td>11910646</td> 
   <td>2014-10-19 14:01:53</td> 
   <td><span style="color:#FF0000;">Accepted</span></td> 
   <td><a href="http://acm.hdu.edu.cn/showproblem.php?pid=1561" rel="nofollow">1561</a></td> 
   <td>0MS</td> 
   <td>400K</td> 
   <td><a href="http://acm.hdu.edu.cn/viewcode.php?rid=11910646" rel="nofollow">1099 B</a></td> 
   <td>C++</td> 
   <td><a href="http://acm.hdu.edu.cn/userstatus.php?user=neopenx" rel="nofollow">Physcal</a></td> 
  </tr> 
 </tbody> 
</table>

转载于:https://www.cnblogs.com/neopenx/p/4034869.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1561]: http://acm.hdu.edu.cn/showproblem.php?pid=1561
[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2364