题解 | #购物单#

购物单

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

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

int main() {
    int N, m, v, p, q, v1, p1, v2, p2;
    cin >> N >> m;
    vector<vector<int>> mainGoods(m + 1);
    vector<vector<vector<int>>> accessories(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> v >> p >> q;
        if (q == 0) {
            mainGoods[i] = vector<int>{v, p};
        }else {
            accessories[q].push_back({v, p});
        }
    }
    vector<vector<int>> dp(m + 1, vector<int>(N + 1));
    int res = 0;
    for (int i = 1; i <= m; i++) {
        if (mainGoods[i].empty()) continue;
        v = mainGoods[i][0];
        p = mainGoods[i][1];
        for (int w = v; w <= N; w += 10) {
            dp[i][w] = max(dp[i][w], (w >= v) ? dp[i - 1][w - v] + v * p : dp[i - 1][w]);
            if (accessories[i].size() >= 1) {
                v1 = accessories[i][0][0];
                p1 = accessories[i][0][1];
                dp[i][w] = max(dp[i][w], (w >= v + v1) ? dp[i - 1][w - v - v1] +
                               v * p + v1 * p1 : dp[i - 1][w]);
                if(accessories[i].size() == 2) {
                    v2 = accessories[i][1][0];
                    p2 = accessories[i][1][1];
                    dp[i][w] = max(dp[i][w], (w >= v + v2) ? dp[i - 1][w - v - v2] +
                                   v * p + v2 * p2 : dp[i - 1][w]);
                    dp[i][w] = max(dp[i][w], (w >= v + v1 + v2) ? dp[i - 1][w - v - v1 - v2] +
                                   v * p + v1 * p1 + v2 * p2 : dp[i - 1][w]);
                }
            }
//             printf("i:%d, w:%d, dp:%d\n", i, w, dp[i][w]);
            res = max(res, dp[i][w]);
        }
    }
    printf("%d\n", res);
    return 0;
}

上述代码存在两个问题：

(1) 错误的continue会导致状态转移不充分！

if (mainGoods[i].empty()) continue;

(2) 对于主件，它参考的是前一项主件，所以对应的dummy状态是dp[i - 1][w]：

dp[i][w] = max(dp[i][w], (w >= v) ? dp[i - 1][w - v] + v * p : dp[i - 1][w]); // 错误
dp[i][w] = (w >= v) ? max(dp[i - 1][w],  dp[i - 1][w - v] + v * p) : dp[i - 1][w]; //正确

而对于附件，它参考的是主件，所以dummy状态是dp[i][w]

dp[i][w] = max(dp[i][w], (w >= v + v1) ? dp[i - 1][w - v - v1] + v * p + v1 * p1 : dp[i - 1][w]); //错误
dp[i][w] = (w >= v + v1)    ?    max(dp[i - 1][w],  dp[i][w - v - v1] + v * p + v1 * p1): dp[i][w]; //正确

正确的代码应该是：

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

int main() {
    int N, m, v, p, q, v1, p1, v2, p2;
    cin >> N >> m;
    vector<vector<int>> mainGoods(m + 1, vector<int>(3, 0));
    vector<vector<vector<int>>> accessories(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> v >> p >> q;
        if (q == 0) {
            mainGoods[i] = vector<int>{v, p};
        }else {
            accessories[q].push_back({v, p});
        }
    }
    vector<vector<int>> dp(m + 1, vector<int>(N + 1));
    int res = 0;
    for (int i = 1; i <= m; i++) {
        v = mainGoods[i][0];
        p = mainGoods[i][1];
        for (int w = 0; w <= N; w += 10) {
            dp[i][w] = (w >= v) ? max(dp[i - 1][w],  dp[i - 1][w - v] + v * p) : dp[i - 1][w];
            if (accessories[i].size() >= 1) {
                v1 = accessories[i][0][0];
                p1 = accessories[i][0][1];
                dp[i][w] = (w >= v + v1) ? max(dp[i][w], dp[i - 1][w - v - v1] +
                               v * p + v1 * p1) : dp[i][w];
                if(accessories[i].size() == 2) {
                    v2 = accessories[i][1][0];
                    p2 = accessories[i][1][1];
                    dp[i][w] = (w >= v + v2) ? max(dp[i][w],  dp[i - 1][w - v - v2] +
                                   v * p + v2 * p2) : dp[i][w];
                    dp[i][w] = (w >= v + v1 + v2) ? max(dp[i][w], dp[i - 1][w - v - v1 - v2] +
                                   v * p + v1 * p1 + v2 * p2) : dp[i][w];
                }
            }
        }
    }
    printf("%d\n", dp[m][N]);
    return 0;
}