餐厅排队取餐问题：优化出餐顺序以获得最高总分

餐厅排队取餐问题：优化出餐顺序以获得最高总分/n/n有 n 个人在排队取餐。每个人都有自己的口味偏好，他们会在手机上自助选择好自己想要的餐品。不同的餐品需要不同的制作时间。/n/n你是这家餐厅的老板，作为生意火爆的网红打卡点，你的餐厅营业时间一天只有 m 分钟。如果某个顾客能够吃到他点的餐品，他会就给餐厅打分。第 i 个人如果吃到了餐品，他就会给餐厅打 x[i] 分。但是由于不能马上吃到餐品，顾客就会产生不满。如果第 i 个人吃到餐品等待了 q 分钟，他就会减少打分，分数就会减少 q * y[i]，这里 y[i] 表示顾客每分钟产生的不满度。并且每个顾客有一个等待爆发周期 z[i]，即每隔 z[i] 分钟会直接降低打分 30 分。当然，只要顾客吃到了餐品，他至少会给餐厅打原本分数的一半。/n/n作为老板，你当然是可以看到所有顾客的要求的。为了让你的餐厅的总分尽量高，你决定调整出餐的顺序。请你根据给出的顾客要求，来安排出餐顺序获得最高的总分。当然不一定每位顾客都能在营业时间内获得餐品。/n/n### 输入格式/n/n第一行输入两个数 n, m，表示共有 n 个人，营业时间为 m 分钟/n/n接下来输入 n 行，每行输入四个数 x[i], y[i], z[i]，t[i]。x[i] 表示第 i 个顾客如果吃到餐品会打的最高分数，y[i] 表示每分钟产生的不满度，z[i] 表示等待爆发周期，每个周期减少 30 分。t[i] 表示制作该餐品所需要花费的时间。/n/n### 输出格式/n/n输出一行一个数，表示获得的最高总分。/n/n### 输入样例/n/n/n2 100/n1000 4 30 50/n500 2 50 50/n/n/n### 输出样例/n/n/n1020/n/n/n### 数据范围/n/n对于 70% 的数据，保证 n ≤ 10/n对于 100% 的数据，保证 n ≤ 20, m ≤ 1000, 1 ≤ x[i] ≤ 10000, 0 ≤ y[i] ≤ 100, 1 ≤ z[i] ≤ 100, 1 ≤ t[i] ≤ 100/n每个顾客初始的最高分数保证是 10 的倍数。/n/n## 算法1/n/n(动态规划 DP) $O(n^2)$/n/n### 思路/n/n首先分类讨论一下：假设我们已经确定了第 i 个人的餐品制作完成时的时间点 $time_i$，那么在此时间点之前，我们可以按照任意顺序制作第 i 个人之前的餐品，而在此时刻之后，由于顾客间相互独立，所以可以按照 $x_i$ 从大到小的顺序制作第 i 个人的餐品。/n/n接下来就是把问题转化为背包问题了，我们把所有的顾客按照结束时间从小到大排序，然后进行 DP。设 $f_{i,j}$ 表示前 i 个人在前 j 分钟内制作餐品所获得的最高总分数。/n/n状态转移方程如下：/n/n- $f_{i,j}=/max(f_{i-1,j}, f_{i-1,j-t_i}+/frac{x_i}{2})$，其中 $j/le time_i$/n- $f_{i,j}=/max(f_{i-1,j}, f_{i-1,j-t_i}+/frac{x_i-y_i/times (j-time_i)}{2})$，其中 $j > time_i$ 且 $j-time_i/ /bmod/ z_i /ne 0$/n- $f_{i,j}=/max(f_{i-1,j}, f_{i-1,j-t_i}+/frac{x_i-y_i/times (j-time_i)-30}{2})$，其中 $j > time_i$ 且 $j-time_i/ /bmod/ z_i = 0$/n/n### 注意/n/n- 由于“在此时间点之前，我们可以按照任意顺序制作第 i 个人之前的餐品，而在此时刻之后，由于顾客间相互独立，所以可以按照 $x_i$ 从大到小的顺序制作第 i 个人的餐品”，所以在计算 $f_{i,j}$ 的时候，我们需要先把前 i 个人中结束时间小于等于 j 的餐品按照 $x_i$ 从大到小的顺序进行排序，然后才能计算第 i 个人的餐品。/n- 注意每个顾客至少会给餐厅打原本分数的一半，即 $f_{i,j}=/max(f_{i,j}, f_{i-1,j-/frac{t_i}{2}}+/frac{x_i}{2})$。/n- 注意 $j/le time_i$ 的情况，此时 $x_i$ 只能拿到 $/frac{x_i}{2}$ 的分数。/n/n### 时间复杂度/n/n$O(n^2)$/n/n### C++ 代码/n/nc++/n// 代码待补充/n/n/n## 算法2/n/n(贪心+优先队列) $O(n/log n)$/n/n算法 1 已经做到了 $O(n^2)$ 的复杂度，那么如何优化呢？我们考虑在状态转移的时候，对于一个 $f_{i,j}$，需要对前 $i-1$ 个人的餐品进行排序得到，而调整第 i 个人的餐品的顺序并不能影响第 1 到 i-1 个人的餐品的顺序，所以我们可以考虑把前 i-1 个人的餐品都按照结束时间从小到大进行排序，然后用一个优先队列维护第 i 个人之前的餐品，每次从中取出结束时间最小的餐品进行 DP。这样做的时间复杂度为 $O(n/log n)$。/n/n### C++ 代码/n/nc++/n// 代码待补充/n/n