题解 | #购物单#

购物单

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)

全部评论

相关推荐

本2硕9,秋招不想努力海投了
小何和:行情再不好也不可能拒绝你,不可能只要双9的
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
下个早班:秒挂就是不缺人
点赞 评论 收藏
分享
评论
11
4
分享

创作者周榜

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