一个非常离谱的题。
首先有结论，如果有 \(w\) 使贪心不为最优解，那么比 \(w\) 小的第一个 \(a_i\)，用贪心法求面值为 \(a_i-1\)，除了最后选的一个数 \(a_j\) 会比原方法多选一个，其余与用动态规划求 \(w\) 面值的选取方式一样。
理论求法过于多，这次我们选择一个通俗易懂的讲法。
如果我们用贪心，那么我们一定会取当前的最大值，那么如果贪心是错的那么我们就不会取当前最大值。
所以我们对于每一位 \(a_i\)，我们要寻找不选它更优的方案，假设贪心中选取 \(a_i\) 后会选择 \(a_j\)，那么动态规划一定会选取 \(a_{i+1}\) 到 \(a_{j-1}\) 的数，如果选取比 \(a_j\) 还小的数，那么一定不会是最优。
证明不会选比 \(a_j\) 小的数：假设我们把贪心中足够个 \(a_j\) 拆成数个 \(a_k(k<j)\)，那么把 \(a_k\) 间互相抵消后，贪心中数只会增加不会减少，因为拆开一次 \(a_j\)，至少会有两个数出现。
所以我们只需找到最小的数满足只取 \(a_{i+1}\) 到 \(a_{j-1}\) 的数且刚好大于 \(a_i\) 可以满足的最小的 \(w\)。
那么求这个就可以先枚举 \(i\)，\(j\)，然后贪心求解。
如何贪心求解呢，首先我们先用面值为 \(a_i-1\) 去拼凑，保证这些数最后凑出来不大于 \(a_i\)，拼凑出来肯定会有余数，那么减去这个余数，加上 \(a_{j-1}\)，由于最后余数肯定小于 \(a_{j-1}\)，所以加上 \(a_{j-1}\) 后一定会大于等于 \(a_i\)。
证明上述贪心正确：因为求出来的余数 \(t\) 一定小于 \(a_{j-1}\)，所以补上那个余数最小花费为 \(t-a_{j-1}\)，不存在利用其他数相加得成。
而这下就会有人问，因为有可能加上一个 \(a_{j-1}\) 会补成之前的一个数 \(a_p\)，其实这不影响，如果补了以后 \(a_{j-1}\) 有剩余，实际上在之前求解就会补上，不存在在后来再补。如果没有剩余，这种解会枚举的时候 \(i\) 到 \(g(p<g<j)\) 时满足这种情况，所以穷举的方法使得算法正确。
然后利用 \(O(n)\) 验证贪心的步数是否大于刚刚拼凑的总步数即可。
最后对于每个可行解，取最小值。
时间复杂度：\(O(n^3)\)。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=405;
int n,a[N],ans=2e9+5;
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 num=a[i]-1,sum=0;
for(int k=i+1;k<=j;k++)
{
sum+=num/a[k];
num%=a[k];
}
int lim=a[i]-1-num+a[j];
sum++;
int tot=0;
for(int k=1;k<=n;k++)
{
tot+=lim/a[k];
lim%=a[k];
}
if(sum<tot)ans=min(ans,a[i]-1-num+a[j]);
}
}
if(ans==2e9+5)ans=-1;
printf("%d",ans);
return 0;
}