hi.选课（树形DP）

[CTSC1997] 选课（树形DP）

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 N N N 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 M M M 门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数 N N N , M M M 用空格隔开。( 1 ≤ N ≤ 300 1 \leq N \leq 300 1≤N≤300 , 1 ≤ M ≤ 300 1 \leq M \leq 300 1≤M≤300 )

接下来的 N N N 行,第 I + 1 I+1 I+1 行包含两个整数 $k_i $和 s i s_i si​, k i k_i ki​ 表示第I门课的直接先修课， s i s_i si​ 表示第I门课的学分。若 k i = 0 k_i=0 ki​=0 表示没有直接先修课（ 1 ≤ k i ≤ N 1 \leq {k_i} \leq N 1≤ki​≤N , 1 ≤ s i ≤ 20 1 \leq {s_i} \leq 20 1≤si​≤20）。

输出格式

只有一行，选 M M M 门课程的最大得分。

样例 #1

样例输入 #1

7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

样例输出 #1

13

样例 #2

样例输入 #2

7  5
2  2
0  1
1  4
2  1
7  1
7  6
0  2

样例输出 #2

15

样例 #3

样例输入 #3

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

样例输出 #3

21

提示说明

代码内容

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//队列
// #include <queue>//堆/优先队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N=1e3+10;
ll h[N],e[N],ne[N],idx;
ll dp[N][N];
ll n,m;

//邻链表
void add(ll a,ll b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

//深搜
void dfs(ll u)
{
    for(ll i=h[u];~i;i=ne[i])// ~i => i!=-1
    {
        ll v=e[i];

        dfs(v);

        //背包问题
        for(ll j=m+1;j>=1;j--)
            for(ll k=0;k<j;k++)
                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
    }
}

int main()
{
    cin>>n>>m;
    
    //头指针初始化为 -1
    memset(h,-1,sizeof h);

    for(ll i=1;i<=n;i++)
    {
        ll fa;
        cin>>fa>>dp[i][1];
        add(fa,i);
    }

    dfs(0);//深搜
    
    //把0号根节点列入必选的范围
    //即要选m+1门课
    cout<<dp[0][m+1]<<endl;
    return 0;
}