题解 | #购物单#

购物单

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

# 学习的别人的代码。。。
n, m = map(int,input().split())
primary, annex = {}, {}
for i in range(1,m+1):
    x, y, z = map(int, input().split())
    if z==0:#主件
        primary[i] = [x, y]
    else:#附件
        if z in annex:#第二个附件
            annex[z].append([x, y])
        else:#第一个附件
            annex[z] = [[x,y]]
m = len(primary)#主件个数转化为物品个数
dp = [[0]*(n+1) for _ in range(m+1)]
w, v= [[]], [[]]
for key in primary:
    w_temp, v_temp = [], []
    w_temp.append(primary[key][0])#1、主件
    v_temp.append(primary[key][0]*primary[key][1])
    if key in annex:#存在主件
        w_temp.append(w_temp[0]+annex[key][0][0])#2、主件+附件1
        v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1])
        if len(annex[key])>1:#存在两主件
            w_temp.append(w_temp[0]+annex[key][1][0])#3、主件+附件2
            v_temp.append(v_temp[0]+annex[key][1][0]*annex[key][1][1])
            w_temp.append(w_temp[0]+annex[key][0][0]+annex[key][1][0])#3、主件+附件1+附件2
            v_temp.append(v_temp[0]+annex[key][0][0]*annex[key][0][1]+annex[key][1][0]*annex[key][1][1])
    w.append(w_temp)
    v.append(v_temp)
for i in range(1,m+1):
    for j in range(10,n+1,10):#物品的价格是10的整数倍
        max_i = dp[i-1][j]
        for k in range(len(w[i])):
            if j-w[i][k]>=0:
                max_i = max(max_i, dp[i-1][j-w[i][k]]+v[i][k])
        dp[i][j] = max_i
print(dp[m][n])

全部评论

相关推荐

身边有人上海、深圳 6、7k 都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 14:10
点赞 评论 收藏
分享
Rena1ssanc...:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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