问题描述
学校实行学分制。每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。学校开设了N(N<300)门的选修课程,每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。
在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号,依次为1,2,3,…。 例如:表中1是2的先修课,2是3、4的先修课。如果要选3,那么1和2都一定已被选修过。
你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
输入格式 Input Format
输入文件的第一行包括两个整数N、M(中间用一个空格隔开)其中1≤N≤300,1≤M≤N。
以下N行每行代表一门课。课号依次为1,2,…,N。每行有两个数(用一个空格隔开),第一个数为这门课先修课的课号(若不存在先修课则该项为0),第二个数为这门课的学分。学分是不超过10的正整数。
输出格式 Output Format
输出文件只有一个数,实际所选课程的学分总数。
样例输入 Sample Input
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
样例输出 Sample Output
13
注释 Hint
算法分析
典型树型DP
有两种方法:
1.构建一颗多叉树,父结点选了才能选子结点,递归调用和指针.
2.将多叉树转化为2叉树(左儿子右兄弟),左儿子必须要有父结点而右儿子不必,递归调用和数组记录.
这里讲第一种:
f[i,j]表示第i个结点为根最多选j个课时得到的最大学分.
初值f[i,j]:=score[i];
对于一个父结点x,它有num个子结点,为son[i].用类似背包的方式处理子结点的加分.则
f[x,j]:=max{f[x,j],f[x,k]+f[son[i],j-k]} 2<=j<=m,0<=i<=num;1<=k<=j
注意对于一开始的输入m应该加1,因为需要设置一个根为0
树型DP。
将N叉树转化成二叉树,在建树过程中就将其转化。
tree[i,j]=max{tree[tree[i].right,j],tree[tree[i].left,k-1]+tree[tree[i].right,y-k]+tree[i].data}
{0<=i<=n,2<=j<=m,1<=k<=j}
原本是多叉树,将它转变成二叉树。如果两节点a,b同为兄弟,则将b设为a的右节点;如果节点b是节点a的儿子,则将节点b设为a的左节点。
【代码】
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
58
59
60
61
62
63
64
65
| #include <stdio.h>
#include <string.h>
#define MAXN 501
typedef struct node
{
int mark;
int l, r;
}tree;
tree a[MAXN];
int f[MAXN][MAXN], lastkid[MAXN];
void dp(int i, int j);
int main()
{
int n, m, i, pre;
scanf("%d%d", &n, &m);
memset(a, 0, sizeof(a));
memset(lastkid, 0, sizeof(lastkid));
for (i = 0; i <= n; i++)
{
a[i].l = a[i].r = a[i].mark = 0;
lastkid[i] = 0;
}
for (i = 1; i <= n; i++)
{
scanf("%d%d", &pre, &a[i].mark);
if (lastkid[pre] == 0) //没有兄弟结点,则成为pre的左子树
{
lastkid[pre] = i;
a[pre].l = i;
}
else //有兄弟结点,成为兄弟结点的右子树
{
a[lastkid[pre]].r = i;
lastkid[pre] = i;
}
}
for (i = 1; i <= m; i++)
dp(a[0].l, i);
printf("%d\n", f[a[0].l][m]);
return 0;
}
void dp(int i, int j)
{
int k;
if (a[i].l != 0) dp(a[i].l, j); //切记,一定要先求其孩子的
if (a[i].r != 0) dp(a[i].r, j);
f[i][j] = a[i].mark;
if (a[i].l != 0 || a[i].r != 0)
{
for (k = 1; k <= j; k++)
if (f[i][j] < (f[a[i].l][k - 1] + f[a[i].r][j - k] + a[i].mark))
f[i][j] = f[a[i].l][k - 1] + f[a[i].r][j - k] + a[i].mark;
}
if (f[i][j] < f[a[i].r][j])
f[i][j] = f[a[i].r][j];
} |