目录
显示
题目链接
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;
}
#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;
}
#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;
}