题目
https://codeforces.com/contest/10/problem/E
一个整数硬币系统，满足c[1] > c[2] > … > c[n]，且c[n] = 1。
对于钱数w，为了用最少的硬币数表示出w，有一种贪心算法：不断地取<=w的最大的c[i]，然后w-=c[i]。例如人民币来说，128就可以表示成100 + 20 + 5 + 1 + 1 + 1，共6张钱，也是最优的。
显然这种贪心算法不一定总能得到最优解。例如货币系统4,3,1，当钱数w=6时，贪心算法会得到4+1+1共3个硬币，但最优解是3+3共2个硬币。
现在给定c[1..n]，问这个硬币系统会不会出现贪心算法得不到最优解的问题。如果会出现，那么求出最小的w，使得贪心算法失效。n<=400，0<=c[i]<=10^9。
题解
这道题就是论文《A Polynomial-time Algorithm for the Change-Making Problem》讨论的问题。下载：https://drive.google.com/file/d/1u8fMFGA4myi2ZgJL3TDoNGe6EHH1w16e/view?usp=sharing
以下内容基本是翻译论文内容。
首先，给定c[1..n]和w，要得到w的最优解，是NP-Hard的。要判断对w来说，贪心算法是否是最优解，也是NP-Hard的（虽然这个问题比上面的问题简单一些）。
但是，判断是否存在某个w使得贪心算法失效，以及求出这个最小的w，却有O(n^3)的多项式解法。这跟前面两个NP-Hard的问题并不矛盾。
首先定义硬币系统为 $C=(c_1,c_2,…,c_n)$ 是一个n维向量。定义一个组合为 $V=(v_1,v_2,…,v_n)$ ，那么 $w=V\cdot C=\sum_{i=1}^nv_ic_i$ 就是这个组合得到的钱数。定义$|V|=\sum_{i=1}^nv_i$。
对于$w$来说，设由贪心算法得到的组合为$G(w)$，最佳组合为$M(w)$。我们的问题就是，求最小的$w$，使得$|G(w)|\gt|M(w)|$。如果有多个最佳组合，$M(w)$为字典序最大的那个。
定义两个$n$维向量的小于关系：$U<V$，代表$U$的字典序小于$V$。定义包含关系$U\subset V$，表示对任意$i$，都有$u_i\le v_i$。
我们可以证明几个性质：
- 如果$a\lt b$，那么字典序$G(a)\lt G(b)$。但对于$M$不具备此性质。
- 对于任意可以表示出$w$的组合$V$，都有$V\le G(w)$。也就是说，贪心算法得到的是字典序最大的$V$。
- 如果$U\subset V$，且$V=G(V\cdot C)$，那么$U=G(U\cdot C)$。根据贪心过程即可证明。
- 如果$U\subset V$，且$V=M(V\cdot C)$，那么$U=M(U\cdot C)$。根据最佳组合的定义即可证明。
假设$w$是最小的满足$|G(w)|\gt|M(w)|$的钱数。我们可以发现，$G(w)$和$M(w)$一定是不相交的，也就是说如果某个位置i上某一个大于0，那么另一个在位置i上一定等于0。这是因为我们找的是最小的$w$。如果某个位置i上$G(w)$和$M(w)$都大于0，那么$w-c_i$就成了一个更小的满足条件的值。
同时字典序$M(w)\lt G(w)$。假设$M(w)$中第一个非0的位置是i，最后一个非0的位置是j，那么对于$G(w)$而言，它在第i位上必须是0。因此$G(w)$必定在1到i-1之间有非0的值，才能保证字典序最大。这也告诉我们，$i\gt1$。
接下来我们证明Theorem 1：$M(w)$ 与 $G(c_{i-1}-1)$ 在1到j-1位都相同，在第j位上比后者大1，在第j+1到n位都等于0。
证明：
因为$G(w)$在1..i-1之间有非0位置，所以 $w\ge c_{i-1}$。
考虑$w-c_j$，因为$w$是最小的贪心算法失效的钱数，那么必有 $M(w-c_j)=G(w-c_j)$。同时可以发现，$M(w-c_j)$ 与 $M(w)$ 只是在第j位相差1。因为，对于$w-c_j$而言，贪心的时候第一个贪到的数是$c_i$，因此 $w-c_j\lt c_{i-1}$
于是我们得到：$w-c_j\lt c_{i-1} \le w$
对于 $c_{i-1}-1$来说，第一个贪心到的数是$c_i$。我们考虑将第i位减去1，得到 $c_{i-1}-1-c_i$，有 $c_{i-1}-1-c_i\lt w-c_i$，因此有 $G(c_{i-1}-1-c_i)<G(w-c_i)=M(w-c_i)$。那么我们在第i位上加上1，不会改变字典序大小，那么就得到 $G(c_{i-1}-1)\lt M(w)$。
另外因为 $c_i-1\ge w-c_j$，那么$G(c_{i-1}-1)\ge G(w-c_j)=M(w-c_j)$。于是我们得到：
$$
M(w-c_j) \le G(c_{i-1}-1) \lt M(w)
$$这里的小于是字典序小于。注意到两头的两项只在第j位差1，并且第j位是 $M(w)$ 的最后的非0位置，因此Theorem 1得证。
那么如何找到最小的$w$呢？O(n^2)枚举i和j，求出$G(c_{i-1}-1)$，然后就可以求出$w$，然后再判断一下$w$是否满足条件即可。总复杂度O(n^3)。
代码
https://codeforces.com/contest/10/submission/149007309
思考
问题来了，如果我没看过这篇论文咋整？好像也没啥办法，能想出来的最多也就限于Theorem 1之前的那部分了。可能通过一些打表观察来找到 $c_{i-1}-1$ 的规律吧。