P2014 选课 题解（树形DP）

题目链接

P2014 选课

解题思路

树形动归，用\(f[i][j]\)表示以\(i\)为根，\(j\)个子节点（不包括自己）的最大学分
首先根据题意建图，用根节点\(0\)将森林连成树。
从根节点开始\(DFS\)遍历，遍历到叶节点后回溯，回溯过程中将\(f[i][j]\)更新，利用背包的思想。
\(DFS\)过程中，\(num\)为离根节点0更近的定点，遍历的\(i\)为\(num\)的子节点，容易得出递推关系式：
\(f[num][j]=max\{f[num][j],f[num][j-k-1]+f[i][k]\}\)。这里的\(j-k-1\)表示以\(num\)为顶点（因为\(num\)可以有多个子树），拥有\(k-1\)个节点的子树。

AC代码

#include<stdio.h>
#include<string.h>
int max(int a,int b){return a>b?a:b;}
int f[310][310],next[310],head[310],s;
int dfs(int num){
    if(head[num]==-1)return 0;//叶节点 
    int i,j,k,sum=0,t;
    for(i=head[num];i!=-1;i=next[i]){//遍历该节点所连边 
        t=dfs(i);//以i为根的子树节点数 
        sum+=t+1;//总和+i 
        for(j=sum;j>=0;j--)//节点个数 
            for(k=0;k<=t&&k<=j-1;k++)//以i为根的子树f[i][k]+i+以num为根的子树f[num][j-1-k] 
                f[num][j]=max(f[num][j],f[num][j-1-k]+f[i][k]);
    }
    return sum;
}
int main(){
    int i,n,m,a;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&s);
        f[i][0]=s;//根节点的学分最大值初始为本身 
        next[i]=head[a];//前向星建有向图 
        head[a]=i;
    }
    dfs(0);//0为根 
    printf("%d",f[0][m]);//以0为根的子树学分最大值 
    return 0;
}