自动搬运

查看原文

来自洛谷，原作者为

	0x3喵酱 菜菜喵喵喵也想变强强

搬运于2025-08-24 22:06:16，当前版本为作者最后更新于2018-11-14 18:48:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看起来这道题虽然有很多人写了题解但并没有太多严谨的数学证明。

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

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

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

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

证明过程

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

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

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

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

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

证明过程

假设存在 $x \in B$ 且满足 $x \notin A$ 。

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

那么必然存在 $a_1,a_2,...a_q \in A$ 可以用来组成 $x$ 并且这些元素都不能被 $A$ 集合内的元素组成（因为如果 $a_i$ 能被 $A$ 集合内其它数组成，那么必然可以用那些数来代替 $a_i$），根据上一个结论我们可以知道 $a_1,a_2,...a_q \in B$ 。

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

所以对于任意 $x \in B$ 必然满足 $x \in A$ ，即 $B \subseteq A$。

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

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

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

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

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

我们知道如果 $x$ 能被前 $i$ 个数组成且组成 $x$ 的数当中包含 $a_i$ 那么 $(x-a_i)$ 也必然能被前 $i$ 个数来组成，那么我们很容易想到定义 $f(x)$ 表示 $x$ 能否被组成，那么根据上面的想法显然有 $f(x) = f(x) \vee 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;
}