P5020 [NOIP2018 提高組] 貨币系統
題目傳送門
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TPR90dNRkT5VFVOBDOsJGcohVYsR2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLzI2Y1MTOilDM4MzNwcDN5UWMyQDOjJmNiNmZycDZ1QzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
解題思路
将貨币系統(n,a)看做集合 A ,貨币系統(m,b)看做集合 B
B集合屬于A集合
那就是一道完全背包了
求出A集合中有多少個 a i a_i ai可以被别的 a i a_i ai組成
那答案就是 n-去重複的 a i a_i ai個數
AC代碼
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n,ans,a[10005],f[1000005];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(f,0,sizeof(f));//初值
f[0]=1;
ans=0;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)//完全背包
{
if(f[a[i]]){ans++;continue;}//能否被組成
for(int j=a[i];j<=a[n];j++)
f[j]|=f[j-a[i]];
}
printf("%d\n",n-ans);//答案
}
return 0;
}