题解 | #购物单#

购物单

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

n, m = map(int,input().split())
temp = [[] for _ in range(m+1)]
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z == 0:
        temp[i] = [x//10,y] + temp[i]
    else:
        temp[z]+= [x//10,y]
temp = list(filter(None, temp))
n = n//10
dp = [0] * (n + 1)
for x in temp:
    for y in range(n,-1,-1):
        price = x[0]
        value = x[1]
        #只有主键
        if y>=price:
            dp[y] = max(dp[y], dp[y-price]+price*value)
        #只有主键+一个键
        if len(x) >= 4:
            price2 = x[0] + x[2]
            if y>=price2:
                dp[y] = max(dp[y], dp[y-price2]+x[0]*x[1] + x[2]*x[3])
        #只有主键+两个键
        if len(x) == 6:
            price3 = x[0] + x[4]
            if y>=price3:
                dp[y] = max(dp[y], dp[y-price3]+x[0]*x[1] + x[4]*x[5])
            price4 = x[0] + x[4] + x[2]
            if y>=price4:
                dp[y] = max(dp[y], dp[y-price4]+x[0]*x[1] + x[4]*x[5]+ x[2]*x[3])  
print(max(dp)*10)

好烦,希望碰不到

全部评论

相关推荐

头像
04-17 09:29
已编辑
湖南农业大学 后端
睡姿决定发型丫:本硕末9也是0offer,简历挂了挺多,只有淘天 美团 中兴给了面试机会,淘天二面挂,美团一面kpi面,中兴一面感觉也大概率kpi(虽然国企,但一面0技术纯聊天有点离谱吧)
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务