题解 | #购物单#

#include <iostream>
using namespace std;

struct attach{
    int value;
    int priority;
    attach():value(0),priority(0){}
    attach(int v,int p):value(v),priority(p){}
};
struct goods{
    int value;
    int priority;
    attach obj[2];
    goods():value(0),priority(0){}
    goods(int v,int p):value(v),priority(p){}
};

int dp[32000][60];
goods shop[60];
attach obj[60][2];

/**
 * dp[i][j]表示在选取前j主件物品总余额为i的情况下所能获得的最大满意度
 * 则dp[n][m]即为要求的最大满意度
 */

int main() {
    int n,m,v,p,q;
    while (cin>>n>>m){
        // 保存物品
        for (int i = 1; i <= m; ++i) {
            cin>>v>>p>>q;
            if (q==0){
                // 主件
                shop[i] = goods(v,p);
            } else{
                // 附件
                if (obj[q][0].priority){
                    obj[q][1] = attach(v,p);
                } else{
                    obj[q][0] = attach(v,p);
                }
            }
        }
        // 主件加入附件
        for (int i = 1; i <= m; ++i) {
            if (obj[i][0].priority) {
                shop[i].obj[0] = obj[i][0];
            }
            if (obj[i][1].priority){
                shop[i].obj[1] = obj[i][1];
            }
        }

        // 动态规划
        int one,two,three,surplus;
        for (int i = 1; i <= m; ++i) {
            for (int j = 10; j <= n; j = j + 10) {
                surplus = j - shop[i].value;
                if (surplus>=0){
                    // 单买主件余额足够
                    one = shop[i].value*shop[i].priority;
                    dp[j][i] = max(dp[j][i-1],dp[surplus][i-1]+one);
                    // 考虑加附件情况
                    surplus = j - (shop[i].value + shop[i].obj[0].value);
                    if (surplus>=0){
                        // 主件+附件1
                        two = shop[i].value*shop[i].priority + shop[i].obj[0].value*shop[i].obj[0].priority;
                        dp[j][i] = max(dp[j][i],dp[surplus][i-1]+two);
                    }
                    surplus = j - (shop[i].value + shop[i].obj[1].value);
                    if (surplus>=0){
                        // 主件+附件2
                        two = shop[i].value*shop[i].priority + shop[i].obj[1].value*shop[i].obj[1].priority;
                        dp[j][i] = max(dp[j][i],dp[surplus][i-1]+two);
                        // 考虑加上所有附件情况
                        surplus = j - (shop[i].value + shop[i].obj[0].value + shop[i].obj[1].value);
                        if (surplus>=0){
                            // 主件+附件1+附件2
                            three = shop[i].value*shop[i].priority + shop[i].obj[0].value*shop[i].obj[0].priority + shop[i].obj[1].value*shop[i].obj[1].priority;
                            dp[j][i] = max(dp[j][i],dp[surplus][i-1]+three);
                        }
                    }
                } else{
                    // 购买当前物品余额不够
                    dp[j][i] = dp[j][i-1];
                }
            }
        }
        cout<<dp[n][m]<<endl;
    }
}