(luogu2014) 选课

发表于 分类于 ，

一道经典树状 dp ## 题目描述:

在大学里的每个学生，为了达到一定的学分， 必须从很多课程里选择一些课程来学习， 有些课程必须在某些课程之前学习

现给出 n (n<=300) 个课程的先修课和学分， 在这 n 门课中选择 m (m<=300) 门学习，求能获得的最大学分

思路:

树状 dp

某一课程的先修课和这门课之间在树上构成了一种父子关系， 可以将这些课组织成一棵树， 并将这颗多叉树转为二叉树 (即记录这个结点的子结点以及下一个兄弟结点), 并构造一个虚拟结点 0 用来表示根结点

设 d (i,j) 为以 i 为根的子树，选择 j 门课的最优解

则答案为 d (son (0),m)

对于每个结点，枚举分配到兄弟和子结点的课程数

代码:

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Mn(305);
const int Mm(305);
int n,m;
int s[Mn]; //学分
int son[Mn],bro[Mn]; //一个点的子结点以及兄弟结点
int d[Mn][Mm]; //以i为根, 可选j门课的最优解
int f(int rt,int k)
{
    if(d[rt][k]!=-1	return d[rt][k];
    if(rt==0||k==0)	return d[rt][k]=0; //边界,当i为空或无课程可供分配时答案为0
    else
    {
        d[rt][k] = f(bro[rt],k);
        for(int i(0);i<k;++i)
            d[rt][k] = max(d[rt][k],f(son[rt],i)+f(bro[rt],k-i-1)+s[rt]); //枚举分配到兄弟和子结点的课程数
        return d[rt][k];
    }
}
int main()
{
    cin >> n >> m;
    int cnt(0);
    for(int i(1);i<=n;++i)
    {
        int k;
        scanf("%d %d",&k,s+i);
        bro[i] = son[k];
        son[k] = i;
    }
    memset(d,-1,sizeof d);
    cout << f(son[0],m);
    return 0;
}