[洛谷 5020][NOIP2018]货币系统

题目链接

https://www.luogu.org/problem/P5020

题解

听说不少人看到这题第一眼就是小凯的疑惑？好吧，我考场上也深陷 exgcd 的错误道路无法自拔。

后来做了一道思路相似的题，也加深了对背包思想的理解。

首先让我们思考一个问题：满足条件的货币系统就一定是原货币系统的子集吗？

答案是肯定的。原因是：现在网友们打算简化一下货币系统。

具体的证明可以参考一下hookan神仙的题解，这里就不再展开讲了。（其实真正的原因是本蒟蒻不会证明）

那么第一个问题就草草解决了。我们接下来用完全背包来实现算法。

事实上，本题的背包过程和筛法的过程是有共同之处的。

如果 \(x\) 能够被表示出来，那么 \(x+k*a_i\) 都是能够被表示的。

我们采用这样的思想，将所有能够表示出来的面值都筛掉，剩下的自然就是化简后的货币系统了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[25005],f[25005];
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  memset(f,0,sizeof(f));
  int n,ans=0;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
   scanf("%d",&a[i]);
  sort(a+1,a+n+1);
  f[0]=1;
  for(int i=1;i<=n;i++)
  {
   if(!f[a[i]])ans++;
   for(int j=a[i];j<=a[n];j++)
    if(f[j-a[i]])f[j]=1;
  }
  printf("%d\n",ans);
 }
 return 0;
}