Luogu2014选课

注意循环顺序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,head[1005],fa[1005],dp[1005][1005],cnt;

struct edge{
    int v,next;
}e[1005];

inline void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void dfs(int u){
    for(int i=head[u];i!=-1;i=e[i].next){
        int v=e[i].v;
        dfs(v);
        for(int j=m;j>=1;j--){
            for(int k=1;k<j;k++){
                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
            }
        }
    }
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);m++;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&fa[i],&dp[i][1]);
        add(fa[i],i);
    }
    dfs(0);
    printf("%d\n",dp[0][m]);
}

Luogu2014选课

原文：https://www.cnblogs.com/Y15BeTa/p/11268727.html