题解 | #购物单#

注意，该题的描述存在误区，所谓附件对应主件的编号，主件不是从0开始计数的，而是所有物件从0开始计数，
这个描述没有10年脑血栓写不出来。

下面的代码我理解错了，以为主件是从0开始计数的，故只通过了一部分测试：

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

void print_vector(vector<vector<int> > & input) {
    for(int i = 1; i < 4; ++i) {
        auto item = input[i];
        for(auto num : item) 
            cout << num << ",";
        cout << endl;
    }
}

int main() {
    int money, num;
    cin >> money >> num;
    cin.ignore();
    money /= 10;
    int res(0);
    string s;
    vector<vector<int>> prices(num + 1, vector<int>(3, 0));
    vector<vector<int>> values(num + 1, vector<int>(3, 0));
    int num_obj = 0;
    int _price(0), _value(0), _idx(0);
    for(int i = 0 ;i < num; ++i) {
        getline(cin, s);
        //cout << s << endl;
        stringstream ss(s);
        ss >> _price >> _value >> _idx;
        _price /= 10;
        //cout << _price << "," <<_value << "," << _idx << endl;
        if(_idx == 0) {
            ++num_obj;
            prices[num_obj][0] = _price;
            values[num_obj][0] = _price * _value;
        } else {
            if(prices[_idx][1] != 0) {
                //cout << "init annex 2"<< endl;
                prices[_idx][2] = _price;
                //cout << prices[_idx][2] << endl;
                values[_idx][2] = _price* _value;
                //cout << values[_idx][2] << endl;
            } else {
                //cout << "init annex 1"<< endl;
                prices[_idx][1] = _price;
                //cout << prices[_idx][1] << endl;
                values[_idx][1] = _price * _value;
                //cout << values[_idx][1] << endl;
            }
        }
    }

    //print_vector(prices);
    //print_vector(values);
    vector<vector<int>> dp(num_obj + 1, vector<int>(money + 1, 0));
    //cout << "num_obj:" << num_obj << ", money:" << money << endl;
    for(int i = 1; i <= num_obj; ++i) {
        int price_primary = prices[i][0];
        int price_annex_1 = prices[i][1];
        int price_annex_2 = prices[i][2];
        int value_primary = values[i][0];
        int value_annex_1 = values[i][1];
        int value_annex_2 = values[i][2];
        //cout << price_primary << ","<< price_annex_1 << ","<< price_annex_2 << endl;
        for(int j = 1; j <= money; ++j) {
            int tmp_max = dp[i-1][j];
            if(j >= price_primary) 
                tmp_max = max(tmp_max, dp[i-1][j-price_primary] + value_primary);
            if(j >= price_primary + price_annex_1) 
                tmp_max = max(tmp_max, dp[i-1][j-price_primary-price_annex_1] +
                            value_primary + value_annex_1);
            if(j >= price_primary + price_annex_2)
                tmp_max = max(tmp_max, dp[i-1][j-price_primary-price_annex_2] +
                            value_primary + value_annex_2);
            if(j >= price_primary + price_annex_1 + price_annex_2)
                tmp_max = max(tmp_max, dp[i-1][j-price_primary
                                                -price_annex_1
                                                -price_annex_2] +
                            value_primary + value_annex_1 + value_annex_2);
            dp[i][j] = tmp_max;
        } 
    }
    res = dp[num_obj][money] * 10;
    cout << res << endl;
    return 0;
}

修改为下面的代码即可AC:

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

void print_vector(vector<vector<int> > & input) {
    for(int i = 1; i < 4; ++i) {
        auto item = input[i];
        for(auto num : item) 
            cout << num << ",";
        cout << endl;
    }
}

int main() {
    int money, num;
    cin >> money >> num;
    cin.ignore();
    money /= 10;
    int res(0);
    string s;
    vector<vector<int>> prices(num + 1, vector<int>(3, 0));
    vector<vector<int>> values(num + 1, vector<int>(3, 0));
    int num_obj = 0;
    int _price(0), _value(0), _idx(0);
    for(int i = 1 ;i < num + 1; ++i) {
        getline(cin, s);
        //cout << s << endl;
        stringstream ss(s);
        ss >> _price >> _value >> _idx;
        _price /= 10;
        //cout << _price << "," <<_value << "," << _idx << endl;
        if(_idx == 0) {
            ++num_obj;
            prices[i][0] = _price;
            values[i][0] = _price * _value;
        } else {
            if(prices[_idx][1] != 0) {
                //cout << "init annex 2"<< endl;
                prices[_idx][2] = _price;
                //cout << prices[_idx][2] << endl;
                values[_idx][2] = _price* _value;
                //cout << values[_idx][2] << endl;
            } else {
                //cout << "init annex 1"<< endl;
                prices[_idx][1] = _price;
                //cout << prices[_idx][1] << endl;
                values[_idx][1] = _price * _value;
                //cout << values[_idx][1] << endl;
            }
        }
    }

    //print_vector(prices);
    //print_vector(values);
    vector<vector<int>> dp(num + 1, vector<int>(money + 1, 0));
    //cout << "num_obj:" << num_obj << ", money:" << money << endl;
    for(int i = 1; i <= num; ++i) {
        int price_primary = prices[i][0];
        int price_annex_1 = prices[i][1];
        int price_annex_2 = prices[i][2];
        int value_primary = values[i][0];
        int value_annex_1 = values[i][1];
        int value_annex_2 = values[i][2];
        //cout << price_primary << ","<< price_annex_1 << ","<< price_annex_2 << endl;
        for(int j = 1; j <= money; ++j) {
            int tmp_max = dp[i-1][j];
            if(j >= price_primary) 
                tmp_max = max(tmp_max, dp[i-1][j-price_primary] + value_primary);
            if(j >= price_primary + price_annex_1) 
                tmp_max = max(tmp_max, dp[i-1][j-price_primary-price_annex_1] +
                            value_primary + value_annex_1);
            if(j >= price_primary + price_annex_2)
                tmp_max = max(tmp_max, dp[i-1][j-price_primary-price_annex_2] +
                            value_primary + value_annex_2);
            if(j >= price_primary + price_annex_1 + price_annex_2)
                tmp_max = max(tmp_max, dp[i-1][j-price_primary
                                                -price_annex_1
                                                -price_annex_2] +
                            value_primary + value_annex_1 + value_annex_2);
            dp[i][j] = tmp_max;
        } 
    }
    res = dp[num][money] * 10;
    cout << res << endl;
    return 0;
}