20241004动态规划

A. 找行李

容易想到一个 \(n^4\) 的 dp: 先把人的位置和行李的位置排序，所以加入 \(i\) 选择了 \(j\) 号行李，那么 \(i\) 以后的人选择 \(j\) 号行李前面的行李，就没有贡献了。设 \(dp_{i,j,k}\) 表示前 \(i\) 人，第 \(i\) 个人选择的是 \(j\) 号行李，在前 \(j\) 个行李中有 \(k\) 个没有被选的。\(n^4 = 500^4 = 6.25*10^{10}\) 明显超时，但是这个 dp 好像不能优化。
需要换一个状态。我们固定这个最早的时间，算对于每个人可以匹配的行李数量。对于时间 \(t（t\in [1,500]）\)，\(dp_i\) 表示第 \(i\) 个人，可以让他成为最早拿到行李的人，可以匹配多少个行李。

B. [POI2015] MYJ

这道题最终的目的是使商家赚的钱最多，所以对于一个价格，它如果取到 \(c_i\) 肯定比不取到优，所以我们不需要考虑 \(c_i\) 具体的值。又注意到 \(n\) 只有 \(50\)，所以可以将 \(c\) 进行离散化。