http://codeforces.com/problemset/problem/10/E
题意
给出货币系统 \(\{c_n\}\) 满足 \(c_1>c_2>\cdots>c_n=1\)，请找到最小的 \(x\) 使贪心算法需要的货币数目比最优解多。
贪心算法：每次取最大的不超过 \(x\) 的货币。
\(1\le n\le400,1\le c_i\le10^9\)
题解
把 \(x\) 的货币系统表示记作向量 \(V\)，即 \(V\cdot C=x\)。
令向量 \(M(x)\) 为表示 \(x\) 字典序最大的最优解，\(G(x)\) 为贪心解（是字典序最大的表示）。
这样限制可以直接比较两个向量。开始推性质（下面的比较都是字典序）：
-
\(\forall x<y,M(x)<M(y)\)
-
\(M\) 的子集是最优的表示，\(G\) 的子集是贪心表示。
这些都由定义易得。
定义 \(s\) 为最小的解，这样取一个子集之后 \(M,G\) 是相等的，可以找一些必要条件：
- \(M(s),G(s)\) 非零位无交。
如果 \(M,G\) 的第 \(i\) 位均大于 \(0\)，\(s-c_i\) 是比 \(s\) 更优的解，矛盾。
设 \(i,j\) 为 \(M(s)\) 的最低和最高非零位。
- \(G(s-c_j)\) 前 \(i-1\) 位为 \(0\)。
\(M(s)\) 前 \(i-1\) 位为 \(0\) \(\Rightarrow\) \(M(s-c_j)\) 前 \(i-1\) 位为 \(0\) \(\Rightarrow\) \(G(s-c_j)\) 前 \(i-1\) 位为 \(0\)。
推论：\(s-c_j<c_{i-1}\)。
- \(G(s)\) 在前 \(i-1\) 位有非零位。
\(G(s)\) 第 \(i\) 位一定是 \(0\)，如果前 \(i-1\) 位也全部是 \(0\)，那么字典序就小于 \(M(s)\) 了，与定义矛盾。
推论：\(s\ge c_{i-1}\)。
现在整理一下限制，因为 \(c_i\) 的数量不多，想要建立和 \(M(s)\) 的关系：
\(s\ge c_{i-1}\Rightarrow c_{i-1}-1-c_i<s-c_i\Rightarrow G(c_{i-1}-1-c_i)<G(s-c_i)=M(s-c_i)\)
发现把向量第 \(i\) 位加 \(1\) 仍是符合定义的。
对于 \(G\) 考虑贪心过程是显然的。
对于 \(M\)，\(M(s-c_i)\) 是 \(M(s)\) 的子集，至少需要再某一位加 \(1\)，必然是第 \(i\) 位。
于是得到 \(G(c_{i-1}-1)<M(s)\)。
从另一个限制出发：
\(s-c_j\le c_{i-1}-1\Rightarrow M(s-c_j)=G(s-c_j)\le G(c_{i-1}-1)\)
本来 \(M(s)\) 字典序大于 \(G(c_i-1)\)，第 \(j\) 位减 \(1\) 后就小于等于了。
首先它们 \(j\) 位之前相等。由于 \(M(s)\) 第 \(j\) 位之后都是 \(0\) ，所以 \(M(s)\) 第 \(j\) 位恰好为 \(G(c_{i-1})\) 第 \(j\) 为加 \(1\)。
现在可以枚举 \(i,j\)，\(O(n)\) check，时间复杂度 \(O(n^3)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
const int inf=2e9;
int main(){
int n,ans=inf;
scanf("%d",&n);
vector<int> c(n);
for(int&x:c) scanf("%d",&x);
auto val=[&](int x){
int res=0;
for(int v:c) res+=x/v,x%=v;
return res;
};
for(int i=1;i<n;i++){
int s=c[i-1]-1,x=s,m=0;
for(int j=i;j<n;j++){
m+=x/c[j];x%=c[j];
if(m+1<val(s-x+c[j])) ans=min(ans,s-x+c[j]);
}
}
printf("%d\n",ans==inf?-1:ans);
return 0;
}