#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    const int maxsize=25000;
    
    int cmp(int x,int y)
    {
        return x<y;
    }
    
    int T,n,m,a[100],f[maxsize+1];
    
    void main()
    {
        scanf("%d",&T);
        for (int RP=1;RP<=T;RP++)
        {
            scanf("%d",&n);
            for (int i=0;i<n;i++)
                scanf("%d",&a[i]);
            sort(&a[0],&a[n],cmp);
            m=0;
            memset(f,0,sizeof(f));
            f[0]=1;
            for (int i=0;i<n;i++)
            {
                m+=f[a[i]]^1;
                if (f[a[i]]==1)
                    continue;
                for (int j=a[i];j<=a[n-1];j++)
                    f[j]=f[j]|f[j-a[i]];
            }
            printf("%d\n",m);
        }
    }
}

int main()
{
    dts::main();
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    const int maxsize=25000;
    
    int cmp(int x,int y)
    {
        return x<y;
    }
    
    int T,n,m,a[100],f[maxsize+1];
    
    void main()
    {
        scanf("%d",&T);
        for (int RP=1;RP<=T;RP++)
        {
            scanf("%d",&n);
            for (int i=0;i<n;i++)
                scanf("%d",&a[i]);
            sort(&a[0],&a[n],cmp);
            m=0;
            memset(f,0,sizeof(f));
            f[0]=1;
            for (int i=0;i<n;i++)
            {
                m+=f[a[i]]^1;
                if (f[a[i]]==1)
                    continue;
                for (int j=a[i];j<=a[n-1];j++)
                    f[j]=f[j]|f[j-a[i]];
            }
            printf("%d\n",m);
        }
    }
}

int main()
{
    dts::main();
}

本蒟蒻就来写一下自己考场上的思路。

我们把货币系统 (n,a)(n,a) 看做集合 AA，货币系统 (m,b)(m,b) 看做集合 BB。

那么我们首先可以猜测 B \subseteq AB⊆A 。

但是这个结论并不好直接证明，在证明这个猜测前我们先来证明另一个猜测 AA 集合内不能被其它数组成的数必然存在于 BB 集合内，这里使用反证法证明。

证明过程

我们设 x\in Ax∈A 且 xx 不能被 AA 集合内除它以外的元素组成。

然后我们假设 x \notin Bx∉B ，那么就说明 BB 集合中必然存在一些元素能够组成 xx 。

那么这些元素至少存在一个不在集合 AA 内并且不能被集合 AA 里的元素组成的数（因为如果不存在的话集合 AA 内的元素就可以组成 xx 了），可以看到这与集合 BB 的定义产生了矛盾。

综上所述， AA 集合内不能被其它数组成的数必然存在于 BB 集合内 。证毕。

通过这个结论我们便可以证明 B \subseteq AB⊆A 这个猜测了。这里同样使用反证法证明。

证明过程

假设存在 x \in Bx∈B 且满足 x \notin Ax∉A 。

根据题目条件，xx 必然可以被 AA 集合内的数字所组成。

那么必然存在 a_1,a_2,...a_q \in Aa
1
​ ,a
2
​ ,...a
q
​ ∈A 可以用来组成 xx 并且这些元素都不能被 AA 集合内的元素组成（因为如果 a_ia
i
​ 能被 AA 集合内其它数组成，那么必然可以用那些数来代替 a_ia
i
​ ），根据上一个结论我们可以知道 a_1,a_2,...a_q \in Ba
1
​ ,a
2
​ ,...a
q
​ ∈B 。

那么也就是说 xx 可以被 BB 集合内的数字组成，那么凡是可以用 xx 组成的数都可以被 BB 集合内的其它数字组成，那么也就是说即便从集合 BB 中去掉 xx 元素也依旧满足条件，这就与 BB 集合的定义矛盾。

所以对于任意 x \in Bx∈B 必然满足 x \in Ax∈A ，即 B \subseteq AB⊆A。

那么做这道题仅仅只需要最后一个证明了，如果你到这里都看懂了的话那应该不难想到最后一个猜测就是在 AA 集合中能被其它数组成的数必然不在 BB 集合内，事实上这个结论很显然，读者只需要稍微想想便可以想出来，这里就不写证明过程了。

那么到这里做这道题的步骤就已经显而易见了，只需要计算出 AA 集合中存在多少个能被其它数组成的数计算出来就行了。

比较好想的是使用搜索算法，相信各位都会，这里就不多说了。主要讲一下使用完全背包来完成这件事。

根据常识，我们知道 xx 只能被比它小的数字组成而不能被比它大的数字组成。

那么很显然，我们可以首先对数组排个序，然后对于每一个数考虑能不能被它前面的数字所组成。

我们知道如果 xx 能被前 ii 个数组成且组成 xx 的数当中包含 a_ia
i
​ 那么 (x-a_i)(x−a
i
​ ) 也必然能被前 ii 个数来组成，那么我们很容易想到定义 f(x)f(x) 表示 xx 能否被组成，那么根据上面的想法显然有 f(x) = f(x) \vee f(x-a_i)f(x)=f(x)∨f(x−a
i
​ )。

那么这个样子也就是最终的解法了，个人认为这道题主要考察对集合相关概念的证明，而重点并不是动态规划，其它的题解侧重点都不太对。

最后贴出AC代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAXAI 25005
#define MAXN 105
int f[MAXAI];
int a[MAXN];
int main()
{
//freopen("money.in","r",stdin);
//freopen("money.out","w",stdout);
int i,j,n,T,ans;
scanf("%d",&T);
while(T--)
{
memset(f,0,sizeof(f));
scanf("%d",&n);ans=n;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
f[0]=1;
for(i=1;i<=n;i++)
{
if(f[a[i]])
{
ans--;
continue;
}
for(j=a[i];j<=a[n];j++)
{
f[j]=f[j]|f[j-a[i]];
}
}
printf("%d\n",ans);
}
return 0;
}