luogu P2014 选课（树形dp）

女爷i 2021-11-05 13:16 389阅读 0赞

[传送门][Link 1]

# 题意： #

现在有很多门课程，但是每门课程都会依赖某些其他的课程（即学了第\\(a\_i\\)门课程之后才能学习第\\(a\_\{i+1\}\\)门课程）。每个课程都有相对应的学分，现在问你选取\\(m\\)个课程最多可以获得多少学分。

# 分析： #

经典的树形依赖背包。根据题意，显然这样会形成一颗森林，而倘若我们把第\\(0\\)号节点作为假根，那么这样的话整张图就形成了一颗有根树。如果形成了这样的依赖状态的话，显然我们必须要先选择叶子结点的课程之后，才能够逐渐的往根部去学习，而现在在我们进行\\(dp\\)的过程中是符合这一条件的，现在我们需要考虑选和不选的状态。不难发现，这个选取\\(m\\)个课程的过程本质上跟背包的性质差不多，因此我们可以设\\(dp\[x\]\[k\]\\)为作为以\\(x\\)为根的子树，现在已经获取了\\(k\\)个课程后的最大的学分。而对于节点\\(x\\)选取了\\(k\\)个课程的状态\\(dp\[x\]\[k\]\\)，他显然是由他的儿子\\(son\[x\]\\)选取了\\(j\\)个课程的状态\\(dp\[son\[x\]\]\[j\]\\)转移而来的，固有状态转移方程：\\(dp\[x\]\[k\]=\\max(dp\[x\]\[k\],dp\[to\]\[j\]+dp\[x\]\[k-j\])\\)。

而在这个过程中，我们需要递归一次，并每次枚举\\(j\\)和\\(k\\)，故总的时间复杂度为：\\(\\mathcal\{O\}(n^3)\\)

# 代码： #

#include <bits/stdc++.h>
    #define maxn 305
    using namespace std;
    struct Node{
        int to,next;
    }q[maxn];
    int head[maxn],cnt=0,val[maxn],dp[maxn][maxn];
    int n,m;
    void add_edge(int from,int to){
        q[cnt].to=to;
        q[cnt].next=head[from];
        head[from]=cnt++;
    }
    void init(){
        memset(head,-1,sizeof(head));
        cnt=0;
    }
    void dfs(int x){
        dp[x][1]=val[x];
        for(int i=head[x];i!=-1;i=q[i].next){
            int to=q[i].to;
            dfs(to);
            for(int j=m+1;j>=1;j--){
                for(int k=0;k<j;k++){
                    dp[x][j]=max(dp[x][j],dp[to][k]+dp[x][j-k]);
                }
            }
        }
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=n;i++){
            int to;
            scanf("%d%d",&to,&val[i]);
            add_edge(to,i);
        }
        dfs(0);
        printf("%d\n",dp[0][m+1]);
        return 0;
    }

转载于:https://www.cnblogs.com/Chen-Jr/p/11205300.html

[Link 1]: https://www.luogu.org/problemnew/show/P2014