洛谷AC 另一个OJ T一个点

P2014 选课

#include<bits/stdc++.h>
using namespace std;
const int N=3e2+5;
vector<int>g[N];
int n,m,mem[N][N],a[N];
int dfs(int u,int v){
	if(mem[u][v]!=-1){
		return mem[u][v];
	}
	if(!v){
		return 0;
	}
	int dp[N]={};
	for(int i:g[u]){
		for(int j=v-1;j>=0;j--){
			for(int k=0;k<=j;k++){
				dp[j]=max(dp[j],dp[j-k]+dfs(i,k));
			}
		}
	}
	return mem[u][v]=dp[v-1]+a[u];
}
int main(){
	cin>>n>>m;
	for(int i=1,f;i<=n;i++){
		cin>>f>>a[i],g[f].push_back(i);
	}
	memset(mem,-1,sizeof(mem));
	cout<<dfs(0,m+1);
}