树形依赖背包

谁借莪１个温暖的怀抱￠ 2021-11-02 09:02 317阅读 0赞

例题：洛谷2014 选课

### 题目描述 ###

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有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**

**思路：一个函数 f\[ x \]\[ j \]是在以x为根的子树上选择j个点的答案，那么f\[ 0\]\[ m \]就是答案。设置y是x的子节点**

**那么状态转移方程  f\[ x\]\[ j \]  =max(f\[ x\] \[ j \],f\[x\]\[j-i\]+f\[ y \]\[ i \]  );**

**自己不擅长背包，所以不明白为什么非要倒序。如果有大佬阅读这个博客 ，希望指点一下。**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<stack>
    #include<bitset>
    #include<cstdlib>
    #include<cmath>
    #include<set>
    #include<list>
    #include<deque>
    #include<map>
    #include<queue>
    using namespace std;
    typedef long long ll;
    const int INF = 1000000000;
    const int M=700;
    int  n,m,val[M],head[M],cnt,f[M][M];
    struct Node{int next,to;}e[M];
    void add(int x,int to){
        e[cnt].to=to;
        e[cnt].next=head[x];
        head[x]=cnt++;
    }
    void dfs(int x){
        f[x][1]=val[x];
        for(int to,i=head[x];~i;i=e[i].next){
            to=e[i].to;
            dfs(to);
            for(int j=m;j;j--)
                for(int k=0;k<j;k++)
                    f[x][j]=max(f[x][j],f[x][j-k]+f[to][k]);
        }
    }
    int main(){
        memset(head,-1,sizeof(head));
        cnt=1;
        scanf("%d%d",&n,&m);
        for(int x,i=1;i<=n;i++){
            scanf("%d%d",&x,&val[i]);
            add(x,i);
        }
        m++;
        dfs(0);
        cout<<f[0][m];
        return 0;
    }