gym101623I Installing Apps
你有 (n) 个应用需要安装，手机共有 (m) 空间，第 (i) 个应用所需下载空间为 (d_i) ，下载完后的安装空间为 (s_i) ，即下载前必须要有至少 (d_i) 剩余空间，安装前必须要有至少 (s_i) 剩余空间，下载完后必须立即安装，下载包会被删掉，即一个应用安装完成后只会占用 (s_i) 空间。找到一种安装顺序，使得能安装的应用数最大
(nleq500; mleq10^4)
考虑只有两个应用 (i, j) 时，如何考虑顺序。若 (s_i+d_j<s_j+d_i) 则 (i) 应当排在 (j) 之前，很好理解（）
照上述比较方式将所有应用排序，解决了顺序问题，之后直接背包即可。可以设状态 (f_{i, j}) 为考虑了排序后前 (i) 个应用，安装 (j) 个应用至少需要多少空间，这样是 (O(n^2)) 的
还有一道经典的题 CF277D Google Code Jam （）
Atcoder Educational DP Contest X - Tower
有 (n) 个物品，每个物品有重量 (w_i) ，承重量 (s_i) ，权值 (v_i) 。你需要从中选任意个物品，按照任意顺序从上到下堆叠，对于选出的任意一个物品 (j) ，需要满足其上方物品重量之和 (leq s_i) ，找到一种合法方案，使得选出物品 (v_i) 之和最大
- (nleq10^3)
- (w_i, s_ileq10^4)
- (v_ileq10^9)
当两个物品 (i, j) 满足 (w_i-s_j<w_j-s_i) 时， (i) 要放在 (j) 上方，因为此时 (j) 作为底部显然能承受更多重量，因此按照 (w_i+s_i) 升序排序，再背包即可
有 (n) 个商店，你在 (0) 时刻在家，从家到任意商店或从一家商店走到另一家商店需要花费 (1) 单位时间。如果你在 (t) 时刻到达了商店 (i) ，你可以花费 (a_i imes t+b_i) 时间购物，你不能在同一个商店多次购物。你想知道在 (T+0.5) 时刻之前你最多能在多少个商店中购物
- (nleq2 imes10^5)
- (a_i, b_i, Tin[0, 10^9])
当只有两个商店 (i, j) ，当前在 (t) 时刻，若先访问 (i) 后访问 (j) ，时间花费为 (t+a_i imes (t+1)+b_i+1+a_j imes(t+1+a_i imes(t+1)+b_i+1)+b_j) ，否则为 (t+a_j imes(t+1)+b_j+1+a_i imes(t+1+a_j imes(t+1)+b_j+1)+b_i) ；因此化简得，当 (a_j(b_i+1)<a_i(b_j+1)) 时， (i) 应当在 (j) 之前访问
但是由于选择购物的商店个数是 (O(n)) 的，不能直接背包。注意到一个性质：对于商店 (i) ，当 (a_i>0) 时，当前时刻 (t) 至少翻倍，因此必定不会访问多于 (log(T)) 个 (a_i>0) 的商店。因此将 (a_i>0) 的商店与 (a_i=0) 的分开考虑，前者的贡献可以由 (nlog T) 背包得出，后者必定会在 (a_i>0) 的商店访问完后才访问，因此拉出来按 (b_i) 升序考虑即可