首页 > 其他分享 >luoguP2014 选课

luoguP2014 选课

时间:2024-11-03 15:41:35浏览次数:1  
标签:std luoguP2014 选课 int dfs vector adj dp

有N门课程,每门课程有0或1门先修课程,课程i的学分为s[i],问选M门课能取得的最大学分是多少?
1<=N<=300; 1<=M<=300; 1<=s[i]<=20

分析:树上01背包,记dp[x][j]表示以x为根的子树最多选j门课的最大学分。对于节点x,如果要选其子节点,则必须选择x。枚举以子节点为根的子树修几门课,进行递推。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
	int N, M;
	std::cin >> N >> M;
	std::vector<int> w(N + 1);
	std::vector<std::vector<int>> adj(N + 1);
	for (int i = 1; i <= N; i++) {
		int x, y;
		std::cin >> x >> y;
		adj[x].push_back(i);
		adj[i].push_back(x);
		w[i] = y;
	}

	std::vector<std::vector<int>> dp(N + 1, std::vector<int>(M + 2));

	auto dfs = [&](auto self, int x, int p) -> void {
		for (int i = 1; i <= M + 1; i++) {
			dp[x][i] = w[x];
		}
		for (auto i : adj[x]) if (i != p) {
			self(self, i, x);
			for (int j = M + 1; j >= 1; j--) {
				for (int k = 0; k < j; k++) {
					dp[x][j] = std::max(dp[x][j], dp[i][k] + dp[x][j - k]);
				}
			}
		}
	};

	dfs(dfs, 0, 0);
	std::cout << dp[0][M + 1] << "\n";
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}

标签:std,luoguP2014,选课,int,dfs,vector,adj,dp
From: https://www.cnblogs.com/chenfy27/p/18523521

相关文章