CF 10 E

CF 10 E

? 给定 n 种货币，每种货币数量无限。 现在要求以最少的货币数目表示一个数 S 。 一种方法是 DP 求一个最优解了， 当然正常人的做法是贪心：每次取最大的不超过当前待表示数的货币。 现在，你的任务是证明正常人的表示法不一定最优：找到最小的 S，使得正常人的表示法比理论最优解差，或说明这样的 S 不存在。

? \(n \leq 400 , a_i \leq 10^9，a_1>a_2>...a_n ~,~ a_n=1\)

? 又是一道大难题，似乎还是个论文题 证明是从论文搬来的。

? 由题可设货币向量 $ C = (a_1,a_2,...,a_n)$ ，设使用集合向量 V 表示出 S ，那么有 \(C \cdot V=S\)

? 定义 size = \(V \cdot (1,1,...1)\)

? 记 x 的贪心表示为 F(x) 即为按题目流程模拟

? 记 x 的最小表示为 G(x) ，即最小化 size 情况下再最小化字典序的表示

? 首先明确一个 非常 重要的性质 对于每个贪心表示/最小表示,它的每个子集也都是贪心表示/最小表示 ，这个条件证明就考虑反证，如果不是那么完全可以在大集合中替换掉一部分方案。这个条件有什么用？下面我们就可以很方便地从一个大集合中删去一个数并且继承大集合的方案。

? 设 w 为最小的反例，设 x 为 G(w) 中下标最小的非零位，y 为 G(w) 中下标最大的非零位

? 那么有结论 ： \(G(w)\) 和 \(F(a_{x-1}-1)\) 在 \([1,y-1]\) 位全相同，在第 y 位前者比后者大 1

? （下文中向量之间的 < , > 均表示它们 字典序 大小的比较）

? 证明：

? ① 由于 w 是反例，那么 F(w) != G(w)，F(w) 的所有非零位和 G(w) 的所有非零位没有相交(如果相交可以根据上文性质将相交位删掉)

? ② F(w) 在 [1,x-1] 位上一定有非零位：如果没有，那么根据贪心流程，x 位应该是非零位，但根据 ① 可知这是不可能的

? ③ 由 ② 可知 \(w \geq a_{x-1}\)

? ④ 由于 w 是最小的反例，那么 \(F(w-a_y)=G(w-a_y)\)，而根据性质 \(G(w-a_y)\) 即为从 \(G(w)\) 中将第 y 个位置删掉 1，所以 [1,x-1] 位等于 0，那么 \(F(w-a_y)\) 的 [1,x-1] 位也等于 0，所以有 \(w-a_y

? ⑤

\[由 ~ ③ ~ 得,w-a_x > a_{x-1}-a_{x}-1\\ \therefore G(w-a_x)=F(w-a_x)>G(a_{x-1}-a_x-1)\\ 逆用性质，得到 ~ F(w)>G(a_{x-1}-1) \]

? ⑥

\[由 ~ ④ ~ 得，w-a_{y}<=a_{x-1}-1\\ \therefore G(w-a_{y})=F(w-a_y)\leq G(a_{x-1}-1) \]

? 最后，结合 ⑤ ⑥，我们发现，将 F(w) 中在 y 位上删去一个，就变得小于等于 \(G(a_{x-1}-1)\) 了，那么说明在 [1,y-1] 位它们都相同，又 \(\because\) F(w) 在 [y+1,n] 上都是 0，那么说明 F(w) 一定是在第 y 位比 \(G(a_{x-1}-1)\) 大 1

? Q.E.D

那么我们利用这个结论，就可以直接枚举这个 x,y 是什么，然后再 O(n) 的 check 一遍，更新答案。

总复杂度 O(n^3)