题解 | #购物单#

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

//物品类
class Object {
  protected:
    //物品编号
    int id;

    //物品价格
    int v;

    //物品重要度
    int p;

    //0或所属主件编号
    int q;

  public:
    //构造函数
    Object(const int j = 0, const int v = 0, const int p = 0, const int q = 0) {
        this->id = j;
        this->v = v;
        this->p = p;
        this->q = q;
        return;
    }

    //析构函数
    ~Object() {}

  public:
    //获取物品编号
    int getid(void)const {
        return this->id;
    }

    //获取物品价格
    int getvalue(void)const {
        return this->v;
    }

    //获取物品重要度
    int getprime(void)const {
        return this->p;
    }

    //判断是否是主件
    bool isSubject(void)const {
        if (this->q)
            return false;
        else return true;
    }

    //获取所属主件编号
    int getSubjectid(void)const {
        if (!this->q)
            cout << "这是主件。" << endl;
        return this->q;
    }

    //获取满意度
    int getSatisfaction(void)const {
        return this->v * this->p;
    }
};

class ShopList {
  private:
    //总钱数
    int N;

    //记录满意度(vvvi[i]j[j][k]表示购买用(j*10)的钱购买前i件物品的状态k的满意度）
    vector<vector<vector<int>>> vvvi;

    //物品列表
    vector<Object> vo;
    vector<vector<Object>> vvo;

  public:
    //构造函数（N为总钱数，m为物品总数
    ShopList(const int N, const int m);

    //析构函数
    ~ShopList();

    //求满意度
    int getSatisfaction(const int i, const int j, const int k)const;

    //最大满意度
    const int getMaxSatisfaction(void);

    //用j*10的钱购买新物品列表前i件物品所能获得的最大满意度
    const int getMaxSatisfaction(const int i, const int j)const;

    //物品列表重构
    void refactObjList(void);

    //填充满意度列表
    void fillSatisfactionVector(void);
};

ShopList::ShopList(const int N, const int m) {
    this->N = N;

    //清空物品列表
    this->vo.clear();

    //用于存储数值
    int v = 0;
    int p = 0;
    int q = 0;

    //录入
    for (int i = 1; i <= m; i++) {
        cin >> v >> p >> q;
        this->vo.push_back(Object(i, v, p, q));
    }
    return;
}

ShopList::~ShopList() {
}

int ShopList::getSatisfaction(const int i, const int j, const int k)const {
    //如果没有钱
    if (j == 0)
        return 0;

    //如果没有物品
    if (i == 0)
        return 0;

    //如果不买
    if (k == 4)
        return this->getMaxSatisfaction(i - 1, j);

    //物品及其附件的价格
    int v = this->vvo[i][0].getvalue() / 10;
    int v1 = this->vvo[i][1].getvalue() / 10;
    int v2 = this->vvo[i][2].getvalue() / 10;

    //如果钱不够买主件
    if (j < v)
        return this->getMaxSatisfaction(i - 1, j);

    //物品及其附件的满意度
    int s = this->vvo[i][0].getSatisfaction();
    int s1 = this->vvo[i][1].getSatisfaction();
    int s2 = this->vvo[i][2].getSatisfaction();

    //如果只买主件
    if (k == 0)
        return s + this->getMaxSatisfaction(i - 1, j - v);

    //如果买主件和附件1
    if (k == 1) {

        //如果钱不够
        if (j < v + v1)
            return this->getMaxSatisfaction(i - 1, j);
        return s + s1 + this->getMaxSatisfaction(i - 1, j - v - v1);
    }

    //如果买主件和附件2
    if (k == 2) {

        //如果钱不够
        if (j < v + v2)
            return this->getMaxSatisfaction(i - 1, j);
        return s + s2 + this->getMaxSatisfaction(i - 1, j - v - v2);
    }

    //如果买主件、附件1和附件2
    if (k == 3) {

        //如果钱不够
        if (j < v + v1 + v2)
            return this->getMaxSatisfaction(i - 1, j);
        return s + s1 + s2 + this->getMaxSatisfaction(i - 1, j - v - v1 - v2);
    }
    return 0;
}

const int ShopList::getMaxSatisfaction(void) {
    this->refactObjList();
    this->fillSatisfactionVector();
    return this->getMaxSatisfaction(this->vvvi.size() - 1, this->N / 10);
}

const int ShopList::getMaxSatisfaction(const int i, const int j) const {
    int max = 0;
    for (int k = 0; k < 5; k++) {
        if (this->vvvi[i][j][k] > max)
            max = this->vvvi[i][j][k];
    }
    return max;
}

void ShopList::refactObjList(void) {
    //在下标为0处置一空数组
    this->vvo.clear();
    this->vvo.push_back(vector<Object>());

    //遍历原物品列表
    for (vector<Object>::iterator voit = this->vo.begin(); voit != this->vo.end();
            voit++) {

        //如果是主件
        if (voit->isSubject()) {
            vector<Object> tmp(1, *voit);
            this->vvo.push_back(tmp);
        }
    }
    for (vector<Object>::iterator voit = this->vo.begin(); voit != this->vo.end();
            voit++) {

        //是附件
        if (!voit->isSubject()) {
            int id = voit->getSubjectid();
            for (int i = 1; i < this->vvo.size(); i++)
                if (this->vvo[i][0].getid() == id) {
                    this->vvo[i].push_back(*voit);
                    break;
                }
        }
    }

    //调整数组大小，避免下标溢出
    for (int i = 0; i < this->vvo.size(); i++)
        this->vvo[i].resize(3);
    return;
}

void ShopList::fillSatisfactionVector(void) {
    for (int i = 0; i < this->vvo.size(); i++) {
        vector<vector<int>> tmp;
        for (int j = 0; j <= this->N / 10; j++) {

            //五种状态：买主件、买主件和附件1、买主件和附件2、买主件和附件1和附件2、不买
            vector<int> vi;
            for (int k = 0; k < 5; k++) {
                vi.push_back(this->getSatisfaction(i, j, k));
            }
            tmp.push_back(vi);
        }
        this->vvvi.push_back(tmp);
    }
    return;
}

int main() {
    int N, m;
    while (cin >> N >> m) { // 注意 while 处理多个 case
        cout << ShopList(N, m).getMaxSatisfaction() << endl;
    }
}
// 64 位输出请用 printf("%lld")