题解【AcWing10】有依赖的背包问题
标签：cin 包含 end 注意 namespace oid ret name 更新
题面
树形 DP 的经典问题。
我们设 \(dp_{i,j}\) 表示当前节点为 \(i\)，当前节点的子树（包含当前节点）最多装的体积是 \(j\) 的最大价值。
我们遍历节点的过程就相当于做了一遍分组背包。
注意遍历完所有子节点后要更新一下状态。
#include
using namespace std;
const int maxn = 103;
int n, m;
int tot, head[maxn], ver[maxn * 2], nxt[maxn * 2];
int dp[maxn][maxn];
int v[maxn], w[maxn], p[maxn];
inline void add(int u, int v)
{
ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void dfs(int u, int f)
{
for (int i = head[u]; i; i = nxt[i]) //循环组数
{
int vv = ver[i];
if (vv == f) continue;
dfs(vv, u); //遍历子节点
for (int j = m - v[u]; j >= 0; j-=1) //循环体积
for (int k = 0; k = v[u]; i-=1) dp[u][i] = dp[u][i - v[u]] + w[u];
for (int i = 0; i > n >> m;
int rt = -1; //根节点
for (int i = 1; i > v[i] >> w[i] >> p[i];
if (p[i] == -1) rt = i;
else add(i, p[i]), add(p[i], i); //建树
}
dfs(rt, 0);
cout
题解【AcWing10】有依赖的背包问题
标签：cin 包含 end 注意 namespace oid ret name 更新
原文地址：https://www.cnblogs.com/xsl19/p/12337084.html
评论