AcWing 532. 货币系统
原题链接
中等
作者:
铁
,
2021-08-30 14:59:01
,
所有人可见
,
阅读 207
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=1e6+100;
int N,M,T;
int c[MAXN];
int f[25010];
int main()
{
ios;
cin>>T;
while(T--){
memset(f,0,sizeof f);
int ans=0;
cin>>N;
for(int i=1;i<=N;i++) cin>>c[i];
sort(c+1,c+1+N);
for(int i=1;i<N;i++){
for(int j=c[i];j<=c[N];j++){
f[j]=max(f[j-c[i]]+c[i],f[j]);
}
if(f[c[i+1]]!=c[i+1]) ans++;
}
cout<<ans+1<<endl;
}
return 0;
}
/*
5
47 329 611 685 940
*/