题解 | #购物单#

购物单

https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4

from collections import defaultdict
line = input().split(" ")
# 除以10是必须的,不然会超时
N = int(line[0]) // 10
m = int(line[1])

prices = defaultdict(lambda: [0, 0, 0])
values = defaultdict(lambda: [0, 0, 0])

for i in range(1, m+1):
    v, p, q = map(int, input().split(" "))
    v //= 10
    # 代表这个是主件
    if q == 0:
        prices[i][0] = v
        values[i][0] = v * p
    elif prices[q][1]:
        prices[q][2] = v
        values[q][2] = v * p
    else:
        prices[q][1] = v
        values[q][1] = v * p

# 开辟一个一维的dp数组
dp = [0] * (N + 1)

for q in prices:
    p1, p2, p3 = prices[q]
    v1, v2, v3 = values[q]
    # 一维数组需要倒序遍历
    for j in reversed(range(N + 1)):
        if j >= p1:
            dp[j] = max(dp[j], dp[j - p1] + v1)
        if j >= p1 + p2:
            dp[j] = max(dp[j], dp[j - p1 - p2] + v1 + v2)
        if j >= p1 + p3:
            dp[j] = max(dp[j], dp[j - p1 - p3] + v1 + v3)
        if j >= p1 + p2 + p3:
            dp[j] = max(dp[j], dp[j - p1 - p2 - p3] + v1 + v2 + v3)

print(dp[N] * 10

全部评论

相关推荐

07-18 18:05
门头沟学院 Java
挂了 正式批求捞
投递滴滴等公司10个岗位
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务