题解 | 加速优化问题

# 分组背包

def main(groups,L,T)->float:
    dp = [(0,0)]
    for choices in groups:
        nxt = []
        for t,c in choices:
            for t0,c0 in dp:
                nxt.append((t+t0,c+c0))
        nxt.sort()
        min_cost = float('inf')
        pruned_nxt = []
        for t,c in nxt:
            if t > T + 1e-9:
                break
            # risk增序，所以在高risk的情况下只有low cost有价值
            if c >= min_cost:
                continue
            min_cost = min(c,min_cost)
            pruned_nxt.append((t,c))
        dp = pruned_nxt
    dp.sort(key=lambda p:p[1])
    return dp[0][1]
        
            


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}")