noip2018 洛谷 P5020 货币系统

noip2018   洛谷  P5020 货币系统

关键: 要使m最小,(m,b)中的数不能用(n,a)中的数表示出来

noip2018   洛谷  P5020 货币系统

对于 3  19  10  6

19=10+3+3+3

6=3+3

只有3 和 10 不能被(n,a)中的数表示

所以m=2

只需要计算出存在多少个能被其它数组成的数计算出来就行了。

法一:完全背包

一个数只能被比它小的数字组成而不能被比它大的数字组成。

可以首先对数组排序,然后对于每一个数考虑能不能被它前面的数字所组成。

若x能够被前i个数组成,那么x-a[i]也能被前i个数组成

f[x]表示x能否被组成

则f [ x ] = f [ x ]  |  f [ x - a [ i ] ]

 #include<bits/stdc++.h>
using namespace std;
const int maxn=;
int main()
{
int a[maxn];
int f[maxn];
int t,n;
int ans;
cin>>t;
while(t--){
memset(f,,sizeof(f));
cin>>n;
ans=n;
for(int i=;i<=n;i++)
cin>>a[i];
sort(a+,a+n+);
f[]=; //边界
for(int i=;i<=n;i++)
{
if(f[a[i]])//a[i]能被前面的数表示
{
ans--;
continue;
}
for(int j=a[i];j<=a[n];j++)
f[j]= (f[j]) | (f[j-a[i]]);
}
cout<<ans<<endl;
}
return ;
}
上一篇:Web大前端面试题-Day1


下一篇:Mac OSX系统、Linux、Windows命令行教程