Python 代码
N, m = map(int, input().split())
N //= 10
childs = [[] for _ in range(m+1)]
things = [0]
for i in range(1, m+1):
v, p, q = map(int, input().split())
v //= 10
things.append([v, p, q])
if q: childs[q].append(i)
def cal_list(idx):
dp = [0] * (N+1)
v1, p1, q1 = things[idx]
for i in range(N, v1-1, -1):
dp[i] = dp[i-v1] + p1 * v1
for child in childs[idx]:
v, p, q = things[child]
for j in range(N, v+v1-1, -1):
dp[j] = max(dp[j], dp[j-v] + p * v)
return dp
f = [0] * (N+1)
for i in range(1, m+1):
v, p, q = things[i]
if q == 0:
list1 = cal_list(i)
for j in range(N, -1, -1):
for k in range(j+1):
f[j] = max(f[j], f[j-k] + list1[k])
print(f[N]*10)