有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