题解 | #购物单#

购物单

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    N /= 10; //缩小后续dp空间(N不是10的整倍数也无妨,省去多出来的余数不影响,因为物品质量全是10的整倍数)
    vector<vector<int>> w(m + 1, vector<int>(3, 0)); //质量(1主件2附件)
    vector<vector<int>> v(m + 1, vector<int>(3, 0)); //价值
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a /= 10;
        b *= a;
        if (c == 0) {
            w[i][0] = a;
            v[i][0] = b;
        } else {
            if (w[c][1] == 0) {
                w[c][1] = a;
                v[c][1] = b;
            } else {
                w[c][2] = a; //此处只能保存该附件值,而无法直接求出主件+附件,因为添加附件时主件可能还未添加
                v[c][2] = b;
            }
        }
    }
    //分组背包
    vector<int> dp(N + 1, 0);
    for (int i = 1; i <= m; i++) {
        for (int j = N; j >= w[i][0]; j--) {
            int p0 = dp[j - w[i][0]] + v[i][0];
            int p1 = j - w[i][0] - w[i][1] >= 0 ? dp[j - w[i][0] - w[i][1]] + v[i][0] + v[i][1] : 0;
            int p2 = j - w[i][0] - w[i][2] >= 0 ? dp[j - w[i][0] - w[i][2]] + v[i][0] + v[i][2] : 0;
            int p3 = j - w[i][0] - w[i][1] - w[i][2] >= 0 ?
                     dp[j - w[i][0] - w[i][1] - w[i][2]] + v[i][0] + v[i][1] + v[i][2] : 0;
            dp[j] = max({dp[j], p0, p1, p2, p3}); //不取/取四种情况里的某一种
        }
    }
    cout << dp.back() * 10;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:33
点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
07-17 11:56
门头沟学院 Java
感谢东子的收留
熬夜脱发码农:无敌了,这是我看到第二个京东的提前批大佬了我还在畏畏缩缩准备八股算法
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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