选课

输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中 $1\leq N\leq 300,1\leq M\leq N,1\leq N\leq 300,1\leq M\leq N$ 。
接下来N行每行代表一门课，课号依次为1，2，…，N。
每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。
学分是不超过10的正整数。

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 860K, 提交时间: 2020-05-17 10:19:26

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int w[N],f[N][N],n,m;
vector<int> v[N];
void dfs(int u)
{
	for(int i=0;i<v[u].size();i++)
	{
		int y=v[u][i];
		dfs(y);
		for(int j=m-1;j;j--)
		for(int k=1;k<=j;k++)
		f[u][j]=max(f[u][j],f[u][j-k]+f[y][k]);
	}
	for(int i=m;i;i--)f[u][i]=f[u][i-1]+w[u];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x>>w[i];
		v[x].push_back(i); 
	}
	m++;
	dfs(0);
	cout<<f[0][m]<<endl;
	return 0;
 }

C++(clang++ 11.0.1) 解法, 执行用时: 13ms, 内存消耗: 768K, 提交时间: 2023-07-19 16:31:06

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
const int N=3e2+5;
vector<int>g[N];
int dp[N][N],n,m,w[N];
void dfs(int u)
{
	dp[u][1]=w[u];
	for(auto v:g[u])
	{
		dfs(v);
		for(int j=m;j>=1;j--)
		for(int k=m;k>=1;k--)
		if(j+k<=m)dp[u][j+k]=max(dp[u][j+k],dp[u][j]+dp[v][k]);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int u;cin>>u>>w[i];
		g[u].push_back(i);
	}m++;
	dfs(0);
	cout<<dp[0][m]<<endl;
}

C++(g++ 7.5.0) 解法, 执行用时: 8ms, 内存消耗: 768K, 提交时间: 2023-07-19 17:07:31

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
const int N=3e2+5;
vector<int>g[N];
int dp[N][N],n,m,w[N];
void dfs(int u)
{
	dp[u][1]=w[u];
	for(auto v:g[u])
	{
		dfs(v);
		for(int j=m+1;j>=0;j--)
		for(int k=0;k<=j-1;k++)
		dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int u;cin>>u>>w[i];
		g[u].push_back(i);
	}
	dfs(0);
	cout<<dp[0][m+1]<<endl;
}

详情