题目链接
P2014 选课 https://www.luogu.org/problemnew/show/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;
- }
P2014 选课 题解(树形 DP)
来源: http://www.bubuko.com/infodetail-2888248.html