@[Guolar_JueMu](/user/476620)
这要看数据强度，对于本题来说，很难，毕竟深度优先搜索的时间复杂度是 $\text{O}(2^n)$，而且在本题环境下似乎并无特别的剪枝措施。
by metaphysis @ 2022-07-09 17:45:47
@[metaphysis](/user/333388) thx
by TempestJueMu @ 2022-07-09 18:36:50
@[metaphysis](/user/333388) 不能记忆化吗 qwq
by j_steady @ 2022-08-05 18:46:01
@[j_steady](/user/559503)
对于典型的01背包问题，即使使用记忆化，当 $n$ 较大时也不可行（例如 $n \ge 32$），因为记忆化是伪多项式的，记忆化只是保证一个状态只解决一次，但是不能减少需要解决的状态数，当 $n$ 较大时，由于状态数以指数级增长，是无法在限定时间内解决的。
by metaphysis @ 2022-08-06 10:03:42
@[metaphysis](/user/333388) 我写的记忆化wa了七个点，大佬有没有空看一下我的代码 qwq （讨论第一篇
by j_steady @ 2022-08-06 11:41:20
@[j_steady](/user/559503)
好的，我看一下再给您回复。
by metaphysis @ 2022-08-06 14:48:52
@[metaphysis](/user/333388) 我用dfs开O2能过，但是不开90pts
by ssjl @ 2022-08-10 19:52:43
@[metaphysis](/user/333388) 这个还能再优化一下么，tle了最后一个
```
#include <iostream>
#include <cstring>
using namespace std;
const int N = 3201;
int n, m;
int f[65][N];
int v[N], w[N], root;
int h[N], ne[N], e[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
for(int i = v[u]; i <= m; i ++)
f[u][i] = v[u] * w[u];
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
dfs(son);
for(int j = m; j >= v[u]; j --)
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()
{
ios::sync_with_stdio(0);
cin.tie(0);
memset(h, -1, sizeof h);
cin >> m >> n;
m /= 10;
root = n + 1;
v[root] = 0, w[root] = 0;
for(int i = 1; i <= n; i ++)
{
int p;
cin >> v[i] >> w[i] >> p;
v[i] /= 10;
if(p == 0) add(root, i);
else add(p, i);
}
dfs(root);
cout << f[root][m] * 10 << '\n';
return 0;
}
```
by ssjl @ 2022-08-10 19:53:54
@[ssjl](/user/745640)
看是否可以记忆化。
by metaphysis @ 2022-08-11 10:15:46
@[metaphysis](/user/333388) 但一共就m个状态 和n没有关系
by ___A__ @ 2023-04-29 22:13:10