树型DP 选课

树型动规 选课

知识点: 树型DP、多叉树转二叉树


多叉树转二叉树表示方式之孩子兄弟链存储结构

孩子兄弟存储结构是为每个节点设计三个域

  1. 一个数据元素域
  2. 一个该节点的第一个孩子节点指针域
  3. 一个该节点下的下一个兄弟节点指针域。
    在这里插入图片描述

描述
学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N(N<300)门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。

在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号,依次为1,2,3,…。 例如:

表中1是2的先修课,2是3、4的先修课。如果要选3,那么1和2都一定已被选修过。   你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

格式
输入格式

输入文件的第一行包括两个整数N、M(中间用一个空格隔开)其中1≤N≤300,1≤M≤N。

以下N行每行代表一门课。课号依次为1,2,…,N。每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。学分是不超过10的正整数。

输出格式
输出文件每行只有一个数。第一行是实际所选课程的学分总数。

样例1
样例输入

1
2
3
4
5
6
5 4
0 1
1 1
2 3
0 3
2 4

样例输出

1
9

样例2
样例输入

1
2
3
4
5
6
7
8
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

样例输出

1
13
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
一道树形dp,因为每门课的先修课最多只有一节,则说明这是个树结构
对于读入的边,我们先将多叉树建立成二叉树
原则是左儿子右兄弟
然后再定义状态f表示以i课程为父亲结点的子树上选j门课程的最多学分
则有状态转移方程
f[i][j]=max(f[left][j-k-1]+f[right][k]+score[i](0<=k<=j-1),f[right][j])
方程含义:1、取当前i节点,则剩下的j-1们课程,在孩子中选j-k-1门,在兄弟中选k门。
2、不取当前节点,则只能在兄弟中选j门。
k用来表示的是分别分配在某个节点上的左右子树的选择课程树
注意还有个f[right][j]即表示不选这门课程而选择它的右兄弟
原理上两种情况是根本上相同可合并的但是实际实现中没有那么方便
所以我们可以自顶向下用dfs进行树的遍历递归求解
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=305;
struct node
{
int l,r,v;
}tree[maxn];
int n,m;
int f[maxn][maxn];

int dfs(int x,int y)
{
if(!y||x<0)
return 0;
if(!x)
return dfs(tree[x].l,y);
if(f[x][y])
return f[x][y];
f[x][y]=dfs(tree[x].r,y);
for(int i=0;i<y;i++)
f[x][y]=max(f[x][y],dfs(tree[x].l,i)+tree[x].v+dfs(tree[x].r,y-i-1));
return f[x][y];
}

int main()
{
memset(tree,-1,sizeof(tree));
cin>>n>>m;
int fa,v;
for(int i=1;i<=n;i++)
{
cin>>fa>>v;
tree[i].r=tree[fa].l;
tree[fa].l=i;
tree[i].v=v;
}
cout<<dfs(0,m)<<endl;//0表示入口,0的子节点表示第一层
return 0;
}