题解 | #购物单#

购物单

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

N, m = input().split()
N, m = int(N), int(m)
goods = []

class Goods:
    def __init__(self):
        self.price = int
        self.value = int
        self.q = int
goods = []
for _ in range(0, m):
    goods.append(Goods())
#负载价值表
w = [[0]*4 for i in range(0,m)]
v = [[0]*4 for i in range(0,m)]

for i in range(0, m):
    a,b,c = input().split(" ")
    temp = goods[i]
    temp.price ,temp.value,temp.q = int(a), int(b), int(c)
    if int(c) == 0:
        w[i][0] = w[i][1] = w[i][2] = w[i][3] = temp.price
        v[i][0] = v[i][1] = v[i][2] = v[i][3] = temp.price * temp.value

#计算好附件的价值
for i in range(0, m):
    if goods[i].q !=0:
        #主件索引等于主件编号-1
        t = goods[i].q -1
        #判断已有附件个数
        #无附件
        if w[t][0] == w[t][1]:
            w[t][1] += goods[i].price
            v[t][1] += goods[i].price * goods[i].value
        #一个附件
        else:
            w[t][2] += goods[i].price
            v[t][2] += goods[i].price * goods[i].value

        w[t][3] += goods[i].price
        v[t][3] += goods[i].price * goods[i].value



# w = [[0*4]*m]
# v = [[0*4]*m]
#dp[i][j]  第i个主件 j预算
dp = [[0]*(N//10+1) for  i in range(0,m+1)]
#主件

for i in range(0,N+1,10):
    count = 0
    for j in  range(0, m):
        p = goods[j].q
        #是主件
        if p == 0:
            count +=1
            # 负载价值表索引为j
            # dp 表预算索引为 i//10
            

            dp[count][i//10]= dp[count-1][i//10]
            for k in  range(0,4):
                if i >= w[j][k]:
                    dp[count][i//10] = max(dp[count][i//10],dp[count-1][i//10-w[j][k]//10]+v[j][k])


print(dp[count][N//10])

全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
07-09 18:28
门头沟学院 Java
写着提前批,结果还要实习4个月以上???
程序员牛肉:这种不用看,直接投了,面试的时候问对应的HR就行。有可能他们是直接复制的暑期实习的模板。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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