sloj P2006. 「树上背包」选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数N, M用空格隔开。( 1≤N≤300 , 1≤M≤300 )

接下来的N行,第I+1行包含两个整数ki​和si​，ki​ 表示第I门课的直接先修课，si​表示第I门课的学分。若 ki​=0 表示没有直接先修课（1≤ki​≤N , 1≤si​≤20）。

输出格式

只有一行，选M门课程的最大得分。

输入输出样例

输入 #1 

7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出 #1 

13

一道非常经典的dp问题，相信大家都做过了，但估计看到这的人都不会树形dp版会了你还看我干吗，还不去多刷几道
接下来谈正事
树形dp大部分都可以用记忆化搜索做的，相信大家这个都会，我就不多谈了
照例，挑战的原因是想作死
问题解析：
每门课程最多只有 1 门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。
如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。
问题就转化：
在一个有 M 个结点的森林中选取 N 个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。
如图 1，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了 1 棵树，
选取结点时，从每个儿子出发进行选取。

这样看来这题和上题差不多：从根开始，把 M+1 个机会分配下去。状态也基本一样，f[i,j] 表示以i 为根的子树中选 j 门课能获得的最大学分。
但这题的树不是二叉的，不能像上题一样枚举分配，于是我们尝试将树转为二叉树，采取左儿子右兄弟的转换方法。具体做法参见代码
左儿子右兄弟写了个n2的蒟蒻
放心，代码里是O(n)
左孩子：原根结点的孩子；
右孩子：原根结点的兄弟
即左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。
因此，我们设 f(i,j) 表示以 i 为根结点的二叉树选 j 门课程的所获得的最大学分，则有
时间复杂度 O(mn2 )
对于这类有限资源分配就类似背包问题，所以这类问题也可以利用树上背包来解决

那么，不多说了，上代码 
#include<bits/stdc++.h>
using namespace std;
struct edge{
    int u,v,w,ne;
}e[100010];
int n,m,h[3010],dp[3010][3010],cnt,son[3010];
void add(int u,int v,int w){
    cnt++;
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].ne = h[u];
    h[u] = cnt;
}
void f(int x){
    for(int i = h[x];i;i = e[i].ne){
        f(e[i].v);
        son[x]+=son[e[i].v];
        for(int j = son[x];j;j--)
            for(int k = 1;k<=son[e[i].v]&&k<=j;k++)
                dp[x][j] = max(dp[x][j],dp[x][j-k]+dp[e[i].v][k]-e[i].w);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n-m;i++){
        int k,x,y;
        scanf("%d",&k);
        for(int j = 1;j<=k;j++){
            scanf("%d%d",&x,&y);
            add(i,x,y);
        }
    }
    memset(dp,128,sizeof(dp));
    for(int i = n-m+1;i<=n;i++){
        int x;
        scanf("%d",&x);
        son[i] = 1;
        dp[i][1] = x;
    }
    for(int i = 1;i<=n;i++)
        dp[i][0] = 0;
    f(1);
    for(int i = m;i>=0;i--)
        if(dp[1][i]>=0){
            printf("%d",i);
            break;
        }
    return 0;
}

 

原文地址：http://www.cnblogs.com/cztq/p/16928186.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性