题解 P2014 【选课】

· · 题解

背包类树形dp

每门课的先修课最多有一门（对应着树中每个节点至多有一个父亲），所以这N门课程构成了森林

因此我们可以引入虚拟0节点作为所有课程的先修课

也就是把N个节点的森林转换成了以虚拟0节点为根的包含N+1个节点的树

具体dp转移方程为背包，详见以下代码

#include<bits/stdc++.h>
using namespace std;
int f[301][301],s[301]={0};
//f[i][j]表示以i为根，选取j门课的最大得分 
int n,m;
vector <int> son[301];
void dp(int x)
{
    f[x][0]=0;//初值：一门都不选学分为0 
    for(int i=0;i<son[x].size();i++)//循环子节点（物品） 
    {
        dp(son[x][i]);//循环更深子树上的选课总门数 
        for(int j=m;j>=1;j--)
            for(int k=j-1;k>=0;k--)//此处使用倒序是为了正确处理体积为0的物品 
                f[x][j]=max(f[x][j],f[x][j-k]+f[son[x][i]][k]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=-0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d%d",&a,&s[i]);
        son[a].push_back(i);//a是i的先修课 //学完a才能学i 
        f[i][1]=s[i];//初值：选自己可以得到的学分 
    }
    m++;//多出一个虚拟0节点作为整棵树的根
    dp(0);//从虚拟0节点开始dp
    printf("%d",f[0][m]);
    return 0;
}