#include using namespace std; //混合背包问题的裸题 const int N = 1010; int f[N]; int main() { //输入+输出重定向 freopen("../1304.txt", "r", stdin); //思路:将多重背包通过二进制转换法变为01背包,然后计算01背包+完全背包即可 int Ts1, Ts2, Te1, Te2, n, m; cin >> Ts1 >> Ts2 >> Te1 >> Te2 >> n; //分钟数 m = Te1 * 60 + Te2 - Ts1 * 60 - Ts2; //模板开始 memset(f, 0, sizeof(f)); int v, w, s; for (int i = 0; i < n; i++) { scanf("%d %d %d", &v, &w, &s); if (s != 0) { // 是多重背包 / 01背包(多重背包特殊情况) if (s == -1) s = 1; // 多重背包特殊情况 s = 1 int num = min(s, m / v); //节省1 for (int k = 1; num > 0; k <<= 1) { // <<=是左移操作 if (k > num) k = num; // 注意这里和for循环的结束条件,可以减少代码量 num -= k; for (int j = m; j >= v * k; j--) { //从大到小枚举 f[j] = max(f[j], f[j - v * k] + w * k); } } } else { // 完全背包,需要从小到大枚举 for (int j = v; j <= m; j++) { f[j] = max(f[j], f[j - v] + w); } } } printf("%d\n", f[m]); //关闭文件 fclose(stdin); return 0; }