（洛谷P2014 选课）<树形DP>

75 阅读 0 评论 50 点赞

我是靠谱客的博主炙热高跟鞋，最近开发中收集的这篇文章主要介绍（洛谷P2014 选课）<树形DP>，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

题目描述

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

树形Dp怎么写呢~调上那么十几二十遍就会了>_>
这个题有两个难点：建树和DP方程
建树：如果能想到将所有的课看成点，先修课是根节点的话，建树就成功了一半；如果能想到将多叉树转为二叉树，整个题就成功了一半。
方法：左儿子右兄弟。即一个节点的左子树原本是它的子节点，也就是它的“后修课”，右子树是它原本的兄弟节点，也就是和它地位相同的课程。
DP方程：f[x][y] 表示在x这个节点及它的子树上，共选择y门课学习的最大学分。
转移：f(x,y)=max(f(node[x].L,i-1)+node[x].c+f(node[x].R,y-i)|1<=i<=y;f[node[x].R][y]);
f[node[x].R][y]表示仅选择它的右子树

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int m,n;
struct tree{
int L,R,c;
}node[600];
int f[600][600];
inline void add(int i,int j){//多叉树转二叉树
node[i].R=node[j].L;
node[j].L=i;
return;
}
int dfs(int x,int y){
if(x<0||y<=0) return 0;
if(f[x][y]>=0) return f[x][y];
if(!x) return dfs(node[x].L,y);//根节点只有右子树
f[x][y]=dfs(node[x].R,y);
for(int i=1;i<=y;++i)
f[x][y]=max(f[x][y],dfs(node[x].L,i-1)+node[x].c+dfs(node[x].R,y-i));
return f[x][y];
}
int main(){
scanf("%d%d",&m,&n);
memset(node,-1,sizeof(node));
memset(f,-1,sizeof(f));
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
add(i,x);
node[i].c=y;
}
//
for(int i=0;i<=m;++i) cout<<node[i].L<<" "<<node[i].R<<" "<<endl;
cout<<dfs(0,n);
return 0;
}