题解 | #购物单#

# 100%已经通过全部测试用例，不解释
import sys
def get_zjbh(line):
    m = int(line.split(" ")[0])
    return m


def f1(zjbh, fj):
    result = []
    for item in fj:
        if zjbh == int(item.split(" ")[3]):
            result.append(item)
    return result


def yanglei(a, b):
    result = []
    for item in a:
        for item2 in b:
            result.append([item, item2])
    return result


def yanglei2(a, b):
    return [a[0] + b[0], a[1] + b[1]]


def get_manyidu(line):
    return int(line.split(" ")[0]) * int(line.split(" ")[1])


def get_new_manyidu(item):
    a = int(item.split(" ")[-1])
    return a


def send(a):
    l = []
    for item in a:
        if item not in l:
            l.append(item)
    l.remove(0)
    l.insert(0, [0, 0])
    return l


def get_money(item):
    a = int(item.split(" ")[1])
    return a


lines = []
count = -1
for line in sys.stdin:
    count = count + 1
    line = line.strip("\n")
    lines.append(str(count) + " " + line + " " + str(get_manyidu(line)))


N = int(lines[0].split(" ")[1])
lines = lines[1:]

# 获取主件列表
zj = []

for line in lines:
    if int(line.split(" ")[3]) == 0:
        zj.append(line)

fj = []
for item in lines:
    if item not in zj:
        fj.append(item)

n = len(zj)
dp = [[i for i in range(5)] for j in range(n)]

i = -1

for line in zj:
    i = i + 1
    money = get_money(line)
    if int(line.split(" ")[1]) < N:
        dp[i][1] = [money, get_new_manyidu(line)]

    zjbh = get_zjbh(line)
    # 判断是否有附件
    tiger = f1(zjbh, fj)
    if tiger == []:
        dp[i][2] = 0
        dp[i][3] = 0
        dp[i][4] = 0
    if len(tiger) == 1:
        dp[i][2] = [
            get_money(tiger[0]) + money,
            get_new_manyidu(tiger[0]) + dp[i][1][1],
        ]
        dp[i][3] = 0
        dp[i][4] = 0

    if len(tiger) == 2:
        dp[i][2] = [
            money + get_money(tiger[0]),
            get_new_manyidu(tiger[0]) + dp[i][1][1],
        ]
        dp[i][3] = [
            money + get_money(tiger[1]),
            get_new_manyidu(tiger[1]) + dp[i][1][1],
        ]
        dp[i][4] = [
            money + get_money(tiger[0]) + get_money(tiger[1]),
            get_new_manyidu(tiger[0]) + dp[i][1][1] + get_new_manyidu(tiger[1]),
        ]


for i in range(len(dp)):
    dp[i] = send(dp[i])

M = [[i for i in range(N, -10, -10)] for j in range(n)]

for j in range(int(N / 10)):
    T=[]
    for v in dp[0]:
        x = N - j * 10
        if v[0] < x or v[0]==x:
            T0 = v[1]
        T.append(T0)
    # print("T", T)
    M[0][j]=max(T)

# print("M[0]",M[0])

for i in range(1, n):
    for j in range(int(N / 10)):
        T = []
        for v in dp[i]:
            x = N - j * 10
            if v[0] > x :
                T0 = M[i - 1][j]

            if v[0] < x or v[0]==x:
                T0 = M[i - 1][int((j * 10 + v[0]) / 10)] + v[1]
            T.append(T0)
        M[i][j] = max(M[i - 1][j], max(T))

print(max(M[n - 1]))