题解 CF10E 【Greedy Change】
题解：
很新颖的题，虽然很老了。
让我们给出反例证明一个假的贪心是假的。
先说一下这个贪心什么时候是对的：假如我们可以加上或减去数列里的一个数，那么这个贪心就是对的。只有加法的话，不对。理由在样例二中已经给的很清楚了。
那么我们只需要模拟两个过程：一个是贪心（可能会假），另一个是自己枚举的反例，找到了就输出，没找到就输出-1.
然后我们思考什么时候可能会有这种假的情况：
找一个面值A，如果有一个比A大一些，但是另一个面值B的整数倍的钱数，那么就有可能使得先选A，剩下的就变得零碎，如果直接用整数个B凑，就能凑齐的情况。
所以我们三重枚举来模拟这个过程即可。
代码：
#include<cstdio>
using namespace std;
int n;
int a[410],ans=-1;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int cnt1=1,cnt2=0,yu=a[i]-1,t;
for(int k=i+1;k<=j;k++)
cnt1+=(yu/a[k]),yu%=a[k];
t=yu=a[i]-1-yu+a[j];
for(int k=1;k<=n;k++)
cnt2+=(yu/a[k]),yu%=a[k];
if(cnt1<cnt2 && (ans==-1||ans>t))
ans=t;
}
printf("%d",ans);
return 0;
}