题解 | 加速优化问题

# 分组背包

def main(groups,L,T):
    global_min = float('inf')
    groups = [[(0,0)]] + groups
    def dfs(cur_i,cur_t,cur_c):
        # print(f"i:{cur_i},t:{cur_t},c:{cur_c},l:{len(groups)}")
        nonlocal global_min
        if cur_c > global_min:
            return
        if cur_t > T + 1e-9:
            return
        if cur_i == len(groups):
            # find solutions
            global_min = min(global_min,cur_c)
            return
        for t,c in groups[cur_i]:
            dfs(cur_i+1,cur_t+t,cur_c+c)
    dfs(0,0,0)
    return global_min
            

if __name__ == "__main__":
    line1 = input().split()
    L,T = int(line1[0]), float(line1[1])
    groups = []
    for _ in range(L):
        line = input().split()
        K = int(line[0])
        choices = []
        for i in range(K):
            t, c = float(line[i*3+2]), float(line[i*3+3])
            choices.append((t, c))
        groups.append(choices)
    res = main(groups,L,T)
    print(f"{res:.2f}")