题解 | #购物单#

这个题好难，看B站视频学会的，官方讲解根本就不是给初学者看的。

一开始没有提前处理，把附件挂在主件下边，然后填dp数组时忽略附件。

我一开始是想给主件做个标记表示已经买过，后来发现会冲突，于是才使用现在的方法，也就是官方视频的方法。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct object {
    int price;//价格
    int val;//重要 1-5
    int belong;//属于x的附件
    int a1;
    int a2;
    void init(int a, int b, int c) {
        price = a;
        val = b;
        belong = c;
    }
    void seta1(int price){
        a1=price;
    }
    void seta2(int price){
        a2=price;
    }
};
int adjust(int& money, object* obj, int count) {
    int min = money;
    int res = 10;
    bool flag = false;
    for (int i = 1; i < count + 1; i++) {
        if (min > obj[i].price) {
            min = obj[i].price;
        }
    }
    obj[0].price = money;
    for (int i = 10; i <= min; i += 10) {
        flag = false;
        for (int j = 0; j < count + 1; j++) {
            if (obj[j].price % i != 0) {
                flag = true;
                break;
            }
        }
        if (flag)continue;
        res = i; //找到最小公因数
    }
    for (int i = 1; i < count + 1; i++) {
        obj[i].price = obj[i].price / res;
    }
    money = money / res; //化简输入
    return res;
}
int main() {
    int money, count; //总钱数，物品总数
    cin >> money >> count;
    int a, b, c;
    object obj[count + 1];
    memset(obj, 0, sizeof(obj));
    obj[0].init(0, 0, 0);
    for (int i = 1; i <= count; i++) {
        cin >> a >> b >> c;
        obj[i].init(a, b, c);
        if(c!=0){//把附件对应到主件
            if(obj[c].a1==0) obj[c].seta1(i);
            else if(obj[c].a2==0) obj[c].seta2(i);
        }
    }
    int rate = adjust(money, obj, count);//返回缩放比例
    int dp[count + 1][money + 1];
    memset(dp, 0, sizeof(dp));
    for (int row = 1; row < count + 1; row++) {
        int price[4];//0 主件 1 附件1 2 附件2 3 附件1加2
        int satisf[4];
        memset(price, 0, sizeof(price));
        memset(satisf, 0, sizeof(satisf));
        //只买主件
        price[0]=obj[row].price;
        satisf[0]=obj[row].price * obj[row].val;
        //买主件和附件1
        if(obj[row].a1>0){
            price[1]=obj[obj[row].a1].price + price[0];
            satisf[1]=obj[obj[row].a1].price * obj[obj[row].a1].val + satisf[0];
        }
        //买主件和附件2
        if(obj[row].a2>0){
            price[2]=obj[obj[row].a2].price + price[0];
            satisf[2]=obj[obj[row].a2].price * obj[obj[row].a2].val + satisf[0];
        }
        //买主件和两个附件
        if(obj[row].a1>0 && obj[row].a2>0)
        {
            price[3]=obj[obj[row].a1].price + obj[obj[row].a2].price + price[0];
            satisf[3]=obj[obj[row].a1].price * obj[obj[row].a1].val + obj[obj[row].a2].price * obj[obj[row].a2].val + satisf[0];
        }
        for (int col = 1; col < money + 1; col++) {
            if(obj[row].belong>0)//是附件
            {
                dp[row][col]=dp[row-1][col];//如果是附件，使用上一行结果
            }
            else 
            {
                if(col>=price[0] && price[0]!=0)//只买主件
                {
                    dp[row][col]=std::max({dp[row-1][col] , dp[row-1][col-price[0]] + satisf[0]});
                }
                else if(col<price[0])//是主件但是钱不够
                {
                    dp[row][col]=dp[row-1][col];
                }
                if(col>=price[1] && price[1]!=0)//买主件和附件1
                {
                    dp[row][col]=std::max({dp[row][col] , dp[row-1][col-price[1]] + satisf[1]});
                }
                if(col>=price[2] && price[2]!=0)//买主件和附件2
                {
                    dp[row][col]=std::max({dp[row][col] , dp[row-1][col-price[2]] + satisf[2]});
                }
                if(col>=price[3] && price[3]!=0)//买主件和附件1 和 附件2
                {
                    dp[row][col]=std::max({dp[row][col],
                                            dp[row-1][col-price[3]] + satisf[3], 
                                            dp[row-1][col-price[2]] + satisf[2],
                                            dp[row-1][col-price[1]] + satisf[1],
                                            dp[row-1][col-price[0]] + satisf[0]});
                }
            }
            //cout<<dp[row][col]<<' ';
        }
        //cout<<"\n";
    }
    cout << dp[count][money] * rate << endl;
}
// 64 位输出请用 printf("%lld")