对于子树而言, 显然能得到的空间上限必然要先剔除掉根节点所占用的空间, 而原版代码还是对整个完整空间m作了dp, 这在带来很多冗余计算量的同时并且让代码对新手不友好, 所以只需要在dfs的时候对当前节点的空间做一下处理, 就能使代码更清晰并且速度加倍.
C++ 代码
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 110;
int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int f[N][N]; // f[i][j] 意思是分配给子树i(包括i这个点本身)空间j的最大价值
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u, int s) // s是分给当前节点u的空间
{
for (int i = h[u]; ~i; i = ne[i]) // 遍历直接子节点
{
int son = e[i];
dfs(son, s - v[u]); // 遍历儿子节点显然要减去当前父节点的要占掉的空间
// 遍历在给当前节点u,u总空间给s的情况下, 如何分配给子树son空间能得到最佳
// 当前的目标是dp选或不选这个son子树分支, 所以是分组后的01背包, 所以从总空间s开始往下
// 值得注意的是, 这个for循环只是在dp所有给son子树空间分配方案之中各种情况的最佳方案, 还没把当前根节点u算进来
for (int j = s; j >= v[son]; j--)
// 这个其实不是平时01背包模型dp的一部分, 只是在枚举子树可能要占的体积
// 平时dp的时候体积都是固定, 在i循环的时候已经读取当的, 这里不一样,体积并不固定
// 这里要分配給子树的体积是这个"子树可能要占的体积", 而
// 只要是比当前j小的体积, 就都是"子树可能要占的体积"
for (int k = 0; k <= j; k++)
f[u][j] = max(f[u][j], f[u][j-k] + f[son][k]);
}
// 当前(上面for循环结束之后)得到的f[u][x]是还没算上当前u的结果, 现在加上
for (int i = s; i >= v[u]; i--) f[u][i] = f[u][i-v[u]] + w[u];
// 根节点都装不下的情况, 在前面提前计算子树的情况可能不为0, 现在要重新置零
for (int i = 0; i < v[u]; i++) f[u][i] = 0;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
int root;
for (int i = 1; i <= n; i ++ )
{
int p;
scanf("%d%d%d", &v[i], &w[i], &p);
if (p == -1) root = i;
else add(p, i);
}
// 根节点得到完整空间
dfs(root, m);
printf("%d\n", f[root][m]);
return 0;
}
然后可以考虑调换下顺序使得更直观
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 110;
int n, m;
int h[N], e[N], ne[N], idx;
int v[N], w[N];
int f[N][N]; // f[i][j] 意思是分配给子树i(包括i这个点本身)空间j的最大价值
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u, int s) // s是分给当前节点u的空间
{
// 先必须分配当前节点
for (int j = s; j >= v[u]; j--)
f[u][j] = w[u];
for (int i = h[u]; ~i; i = ne[i]) // 遍历直接子节点
{
int son = e[i];
dfs(son, s - v[u]); // 遍历儿子节点显然要减去当前父节点的要占掉的空间
// 遍历在给当前节点u,u总空间给s的情况下, 如何分配给子树son空间能得到最佳
// 当前的目标是dp选或不选这个son子树分支, 所以是分组后的01背包, 所以从总空间s开始往下, 下限是v[son]+v[u]
// 值得注意的是, 这个for循环只是在dp所有给son子树空间分配方案之中各种情况的最佳方案, 还没把当前根节点u算进来
for (int j = s; j >= v[son] + v[u]; j--)
// 这个其实不是平时01背包模型dp的一部分, 只是在枚举子树可能要占的体积
// 平时dp的时候体积都是固定, 在i循环的时候已经读取当的, 这里不一样,体积并不固定
// 这里要分配給子树的体积是这个"子树可能要占的体积", 而
// 只要是比当前可用体积小的体积, j - v[u], 就都是"子树可能要占的体积"
for (int k = 0; k <= j - v[u]; k++)
f[u][j] = max(f[u][j], f[u][j-k] + f[son][k]);
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
int root;
for (int i = 1; i <= n; i ++ )
{
int p;
scanf("%d%d%d", &v[i], &w[i], &p);
if (p == -1) root = i;
else add(p, i);
}
dfs(root, m);
printf("%d\n", f[root][m]);
return 0;
}