P2732 USACO 3.3 商店购物

题目传送门：P2732 [USACO3.3]商店购物 Shopping Offers

这道题初看时令人完全无法理解，再仔细阅读后才明白题意，第三次审视时意识到这是一道动态规划问题，经过长时间的思考后，最终想出了一种极为直接但略显粗暴的解决方式。

首先，我将注意力放在小规模数据上，最多仅包含 5 种物品，因此决定采用五维动态规划的方式进行处理。

f[i][j][k][l][m] 表示在第一种物品数量为 i、第二种物品数量为 j、第三种物品数量为 k、第四种物品数量为 l、第五种物品数量为 m 的情况下所对应的最低花费。接下来的工作就变得相对简单，只需按照完全背包问题的思路进行处理即可。

然而，在实际操作过程中我们发现还存在一个令人困扰的问题——编号的处理。如何应对这一难题呢？

我的应对策略类似于离散化方法。将每一个原始编号映射到一个更小的数值上。具体而言，若当前编号 i 在 lsh 数组中尚未被记录（即 lsh[i]==0），则为其分配一个新的编号；反之，则沿用已有的对应值。初始状态下，所有元素在 lsh 数组中均为 0。例如，在如下一组编号：

112 293 112 737

第一个数字是全新的，于是设置 lsh[112]=1；第二个数字也是新