题解 | #购物单#

参照“华科不平凡”的解题代码，把空间复杂度降低为O(n)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    // 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    N /= 10;
    vector<vector<int> > prices(61, vector<int>(3, 0));        // 价格
    vector<vector<int> > priceMultiplyPriority(61, 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) {
            prices[i][0] = a; priceMultiplyPriority[i][0] = b;
        } else {
            if (prices[c][1] == 0) {
                prices[c][1] = a; priceMultiplyPriority[c][1] = b;
            } else {
                prices[c][2] = a; priceMultiplyPriority[c][2] = b;
            }
        }
    }
    // 使用分组背包
    vector<int>dp(N+1, 0);
    for (int i = 1; i <= m; ++i) {
        for (int j = N; j >=0; j--) {
            int a = prices[i][0], b = priceMultiplyPriority[i][0];
            int c = prices[i][1], d = priceMultiplyPriority[i][1];
            int e = prices[i][2], f = priceMultiplyPriority[i][2];
            dp[j] = j >= a ? max(dp[j-a] + b, dp[j]) : dp[j];
            dp[j] = j >= (a+c) ? max(dp[j-a-c] + b + d, dp[j]) : dp[j];
            dp[j] = j >= (a+e) ? max(dp[j-a-e] + b + f, dp[j]) : dp[j];
            dp[j] = j >= (a+c+e) ? max(dp[j-a-c-e] + b + d + f, dp[j]) : dp[j];
        }
    }
    cout << dp[N]* 10 << endl;
}