题解 P5020 【货币系统】

· · 题解

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

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

我们把货币系统 (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;
}