选课

输入的第一行包括两个正整数M,N，分别表示待选课程数和可选课程数。
接下来M行每行描述一门课，课号依次为 $1,2, \cdots,M$ 。每行两个数，依次表示这门课先修课课号（若不存在，则该项值为0）和该门课的学分。
各相邻数值间以空格隔开。

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 740K, 提交时间: 2020-01-09 17:39:32

#include <cstdio>
#include <algorithm>

const int N = 1100;
int n, m;
int hd[N], nt[N], to[N], cnt;
int sc[N];
int f[N][N];//f[i][j]表示以i为根的子树选j门课的最大学分 

void dp(int u) {
	for (int i=hd[u], v; i; i = nt[i]) {
		dp(v = to[i]);
		for (int j = m; j >= 1; --j)//枚举可选的课程数 
			for (int k = 1; k <= j; ++k)
				f[u][j] = std::max(f[u][j], f[u][j-k]+f[v][k]);
	} if (u)
		for (int i = m; i >= 0; --i)
			f[u][i] = f[u][i-1] + sc[u]; 
	
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1, u, s; i <= n; ++i) {
		scanf("%d%d", &u, &sc[i]);
		to[++cnt] = i, nt[cnt] = hd[u], hd[u] = cnt;
	}
	
	dp(0);
	
	printf("%d", f[0][m]);
	
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 768K, 提交时间: 2023-07-31 00:25:56

#include<bits/stdc++.h>
using namespace std;
int n,m,s[301],e[301],head[301],f[301][302];
void dfs(const int &u){
	f[u][1] = s[u];
	int i,j,k;
	for (i = head[u];i;i = e[i]){
		dfs(i);
		for (j = m + 2;--j;)
			for (k = 1;k <= j;k++)
				f[u][j] = max(f[u][j],f[u][k] + f[i][j - k]);
	}
}
int main(){
	memset(f,-0x3f,sizeof(f));
	int k,i;
	cin>>n>>m;
	for (i = 1;i <= n;i++){
		cin>>k>>s[i];
		e[i] = head[k];
		head[k] = i;
	}
	dfs(0);
	cout<<f[0][m + 1];
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 516K, 提交时间: 2023-07-19 16:48:55

#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>=1;j--)
		for(int k=m+1;k>=1;k--)
		if(j+k<=m+1)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);
	}
	dfs(0);
	cout<<dp[0][m+1]<<endl;
}

详情