(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;
}