题解 | #购物单#

购物单

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

money,length = map(int,input().split())
money //= 10
goods = dict()
for i in range(1,length+1):
    v,p,q = map(int, input().split())
    v //= 10
    if q == 0:
        if i not in goods.keys():
            goods[i] = [[v, v*p], [0, 0], [0, 0]]
        else:
            goods[i][0] = [v, v*p]
    else:
        if q not in goods.keys():
            goods[q] = [[0, 0], [v, v*p], [0, 0]]
        elif goods[q][1] == [0, 0]:
            goods[q][1] = [v, v*p]
        else:
            goods[q][2] = [v, v*p]
dp = [0]*(money+1)
for k,v in goods.items():
    for j in range(money ,v[0][0]-1 ,-1):
        dp[j] = max(dp[j],dp[j-v[0][0]] + v[0][1])
        if j >= v[0][0]+v[1][0]:
            dp[j] = max(dp[j],dp[j-v[0][0]-v[1][0]] + v[0][1]+v[1][1])
        if j >= v[0][0]+v[2][0]:
            dp[j] = max(dp[j],dp[j-v[0][0]-v[2][0]] + v[0][1]+v[2][1])
        if j >= v[0][0]+v[1][0]+v[2][0]:
            dp[j] = max(dp[j],dp[j-v[0][0]-v[1][0]-v[2][0]] + v[0][1]+v[1][1]+v[2][1])
print(dp[money] * 10)

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
07-14 12:29
门头沟学院 Java
后端岗,实习三周感觉有点想跑路了,担心秋招被拉黑,有没有佬是字节HR知道情况的
从零开始的转码生活:你实习三周都想跑路,将来拿到offer真的愿意在这干十几二十年吗
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
12
4
分享

创作者周榜

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