题解 | 加速优化问题

import sys

data = sys.stdin.read().strip().split()
it = iter(data)
L = int(next(it))
T = float(next(it))
total_options = []

for _ in range(L):
    K = int(next(it))
    options = []
    for _ in range(K):
        method = next(it)
        t = float(next(it))
        cost = float(next(it))
        options.append((t, cost))
    total_options.append(options)

# 当前最优状态{threshold : cost}
dp = {0.0: 0.0}


for options in total_options:
    new_dp = {}
    for bt, bcost in dp.items():
        for t, cost in options:
            if bt + t > T:
                continue
            nt = bt + t
            ncost = bcost + cost
            if nt not in new_dp or ncost < new_dp[nt]:
                new_dp[nt] = ncost
    dp = new_dp
ans = min(dp.values())
print(f'{ans:.2f}')