问题描述
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了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]; } |