[Leaf] [P5020] 货币系统

luogu-p5020-货币系统">Luogu-P5020 货币系统

1. 题面梗概

中译中: 给你一个硬币集合 $A$，你要找一个最小的集合 $B$，使得 $B$ 能凑出来的钱和 $A$ 能凑出来的钱一模一样。求 $B$ 里面最少有几个数。

2. 逻辑推导

看到这个题，第一反应是：感觉像是线性代数中的求基，但在数论背景下，我们需要深入分析。

直觉：我猜测我们要找的 $B$ 集合应该是 $A$ 集合的一个子集，但直觉归直觉，我们需要通过逻辑证明:

2.1 反证法

1. 我们先证明：$A$ 集合中不能被其他元素组成的数，必然存在于 $B$ 集合中。

   • 设 $x \in A$ 且 $x$ 不能被 $A$ 集合外除它以外的元素组成。若 $x \notin B$，那么就说明 $B$ 集合中必然有一组数能够组成 $x$。

   • 那么这组数中至少存在一个不在 $A$ 集合内，且无法被 $A$ 集合中组成的数，矛盾。

2. 接着就可以证明 $B \subseteq A$。

   • 设 $x \in B$ 且 $x \notin A$。由于 $B$ 和 $A$ 等价，那么 $x$ 必然能被 $A$ 中的数字组成。而这些数字又属于 $B$。
   • 这意味着 $x$ 能被 $B$ 中的其他数组组成，那么 $B$ 去掉 $x$ 后依然等价，这与 $B$ 的定义矛盾。

结论：$B$ 就是从 $A$ 中剔除掉所有能被其他数组成的元素后剩下的集合。

2.2 解决

根据数学常识，一个数 $x$ 只能被比它小的数组成。那么很显然我们只要先将数组排个序，然后考虑每个数能不能被前面的数字组成即可。

写到这里就很明显了，我们可以用搜索，也可以用背包DP，这里我采用完全背包来解决。

DP：$f[x]$ 表示 $x$ 这个数能否被组成。$f[x] = f[x] \vee f[x-a_i]$。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;

const int maxdp = 25000 + 50;
const int maxn = 100 + 5;

int dp[maxdp];
int a[maxn];
int n;

int main( )
{	
    int T;
    cin >> T;
    while( T -- )
    {
        memset( dp, 0, sizeof( dp ) );
        cin >> n;
        int ans = n;

        for( int i = 1; i <= n; ++ i )
        {
            cin >> a[i];
        }
        sort( a + 1, a + n + 1 );
        
        dp[0] = 1;
        for( int i = 1; i <= n; ++ i )
        {
            if( dp[ a[i] ] )
            {
                ans --;
                continue;
            }
            for( int j = a[i]; j <= a[n]; ++ j )
            {
                dp[j] = dp[j] | dp[ j - a[i] ];
            }
        }
        
        cout << ans << '\n';
    }    
    return 0;
}

4. 复盘

• 复杂度: $O( T \cdot N \cdot \max(A) )$。

• 碎碎念: 这题的价值在于理解集合的关系，然后才是完全背包DP解决最后一步。

• 关联笔记: 背包DP