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

题目链接

https://www.luogu.org/problemnew/show/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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注