//【P1064】金明的预算方案 - 洛谷 - 100 #include <iostream> #include <algorithm> const int kMaxN = 32000, kMaxM = 60; // 常量名前带 k，符合命名规范 int v[kMaxM + 5][3], p[kMaxM + 5][3]; int f[kMaxN + 5]; int main() { int n, m; std::cin >> n >> m; for (int i = 1; i <= m; ++i) { int _v, _p, _q; std::cin >> _v >> _p >> _q; if (!_q) { // 是主件 v[i][0] = _v; p[i][0] = _p; } else { if (v[_q][1] == 0) { // 是第一个附件 v[_q][1] = _v; p[_q][1] = _p; } else { // 是第二个附件 v[_q][2] = _v; p[_q][2] = _p; } } } for (int i = 1; i <= m; ++i) for (int j = n; j >= 0; --j) { // 用 lambda 表达式代替函数定义（C++11 偷懒专用) auto cost2 = [v, p, i](int x, int y) { return v[i][x] + v[i][y]; }; auto cost3 = [v, p, i](int x, int y, int z) { return v[i][x] + v[i][y] + v[i][z]; }; auto rpp = [v, p, i](int x) { return v[i][x] * p[i][x]; }; if (j >= v[i][0]) // 够买主件 f[j] = std::max(f[j], f[j - v[i][0]] + rpp(0)); if (j >= cost2(0, 1)) // 还够买第一个附件 f[j] = std::max(f[j], f[j - cost2(0, 1)] + rpp(0) + rpp(1)); if (j >= cost2(0, 2)) // 还够买第二个附件 f[j] = std::max(f[j], f[j - cost2(0, 2)] + rpp(0) + rpp(2)); if (j >= cost3(0, 1, 2)) // 还够买两个附件 f[j] = std::max(f[j], f[j - cost3(0, 1, 2)] + rpp(0) + rpp(1) + rpp(2)); } std::cout << f[n] << std::endl; }