刚接触树状DP,好难啊QAQ

[CTSC1997] 选课

题目描述

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

输入格式

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

接下来的 N 行,第 +1I+1 行包含两个整数 ki​和 si​, ki​ 表示第I门课的直接先修课，si​ 表示第I门课的学分。若 =0ki​=0 表示没有直接先修课（1≤≤1≤ki​≤N , 1≤≤201≤si​≤20）。

输出格式

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

输入输出样例

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

13

//本题略有变形,多加思考
#include<bits/stdc++.h>
using namespace std;
const int N=2020;
int f[N][N],w[N]={1},v[N],h[N],e[N],ne[N],idx,res,n,m,root;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int son=e[i];
        dfs(son);
        for(int j=m;j>=0;j--)//这里为什么要从m开始呢?
    //如标题所示,这个是树状dp的问题,但是按照题意来的话,画完图之后很明显是森林
    //这个时候我们就需要多建立一个0节点来使他们形成树
            for(int k=0;k<=j;k++) f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
    }
    for(int i=m+1;i>=1;i--) f[u][i]=f[u][i-1]+v[u];
    f[u][0]=0;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<=m+1;i++) f[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        int p;
        cin>>p>>v[i];
        //f[i][1]=v[i];
        add(p,i);
    }
    dfs(0);
    cout<<f[0][m+1];//这里的m+1就是因为多建了个节点,0节点是必须选的,但是呢0节点的价值是0;
    return 0;
}