【比赛】NOIP2018 货币系统

可以发现最后的集合一定是给定集合的子集

所以就变成了裸的背包嘛，对于每个数判断它能不能被其它数表示出来，如果可以，就表示这个数是没用的，可以去掉

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define ft first
#define sd second
#define pb(a) push_back(a)
#define mp(a,b) std::make_pair(a,b)
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=100+10,MAXM=25000+10;
int T,n,a[MAXN],f[MAXM],ans,lt;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline bool chkmin(T &x,T y){return y<x?(x=y,true):false;}
template<typename T> inline bool chkmax(T &x,T y){return y>x?(x=y,true):false;}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
int main()
{
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
read(T);
while(T--)
{
read(n);ans=lt=0;
REP(i,1,n)read(a[i]),chkmax(lt,a[i]);
std::sort(a+1,a+n+1);
n=std::unique(a+1,a+n+1)-a-1;
REP(i,1,lt)f[i]=0;f[0]=1;
REP(i,1,n)REP(j,a[i],lt)f[j]+=f[j-a[i]],chkmin(f[j],2);
REP(i,1,n)if(f[a[i]]>1)ans++;
write(n-ans,'\n');
}
return 0;
}