更好的阅读体验

感觉这道题重点不是 DP 是证明……很多高赞题解都是直接上结论的……

比如你考场的时候，想到了这个解法，如果用了怕结论是错的，得分还不如部分分；不用又怕错失正解，其实是很纠结的……所以我这里就写一写证明过程吧，其实也不难。

Statement

有 $n$ 种不同面值的货币，第 $i$ 种面值为 $a[i]$ ，每种无限张。

将一个有 $n$ 种货币、面值数组为 $a[1\dots n]$ 的货币系统记作 $(n,a)$ .称两个货币系统 $(n,a),(m,b)$ 等价，当且仅当对于任意 $x\in N$ ，要么均能被两个货币系统表示出来，要么不能被任何一个表示。

给定一个货币系统 $(n,a)$ ，找到一个最小的 $m$ 使得存在货币系统 $(m,b)$ 与 $(n,a)$ 等价。

$n\leq 100,a[i]\leq 25000$ .

Thoughts & Solution

有一个很显然的想法：答案中的系统方案一定是由原先的系统方案去掉若干种货币得到

事实上这就是正确的。

Proof

令给出的系统中的货币面值为 $A$ 集合，需要得到的货币面值为 $B$ 集合。

引理：$A$ 集合中不能被其他数组成的数一定会在 $B$ 集合中出现。

引理的证明：设有一个数 $x\in A$ 且不能被 $A$ 集合中其他数凑出来。 根据等价，如果 $x\notin B$ ，那么 $B$ 中的其他数一定能组成 $x$ .这就说明 $B$ 中至少存在一个不属于 $A$ 集合且不能被 $A$ 组合出来的数（不然 $A$ 集合就一定能合成 $x$ ），那么这个数本身不属于 $A$ 能组成的范畴，却属于 $B$ 能组成的范畴，就不符合题意了。所以 $x\in B$ ,引理正确性证毕。

那么现在我们需要证明：$B\subseteq A$ .

仍然采用反证法。设存在一个数 $x$ 满足 $x\in B$ 且 $x\notin A$ .

根据题意，显然 $x$ 能被 $A$ 中若干个 $a_1,a_2,\dots ,a_k$ 组成（假定这些数不能被拆分成 $A$ 中其他的数，如果能拆分就直接拿拆分方案替换即可）。根据引理，这些数都属于 $B$ ，也就是说，$B$ 完全可以通过这些数组成 $x$ ，那么 $B$ 中再存在一个 $x$ 显然就是多余的，和 $B$ 集合最小的要求不符。

Q.E.D.

接下来的事情就非常简单了。我们只需要考虑 $A$ 集合中哪些数是多余的就好了。

题目暗示：现在网友们打算 简化 一下货币系统。这说明就是在原基础上去掉某些数（

这个事情可以一次 DP 解决。观察到 $a[i]$ 的范围只有 $25000$ ，那么可以直接设 $f[i]$ 表示 $i$ 这个数能否被前面已经出现过的 $a[j]$ 组成。

• 如果枚举到 $a[i]$ 时，$f[a[i]]=1$ ，那么直接计入答案并跳过即可；
• 如果没有，那么枚举所有的 $j=a[i]\sim mx$ ，$f[j]|=f[j-a[i]]$ （就是用 $j-a[i]$ 和 $a[i]$ 组成 $j$ ，枚举范围中的 $mx$ 表示所有 $a[i]$ 中的最大值）

完结散花 (｡･∀･)ﾉﾞ

注意题目中给出的 $a$ 数组不一定有序，要记得排序。

//Author: RingweEH
const int N=110,M=25010;
int n,a[N],f[M];

int main()
{
    int T=read();
    while ( T-- )
    {
        n=read(); 
        for ( int i=1; i<=n; i++ )
            a[i]=read();

        sort( a+1,a+1+n ); int mx=a[n];
        memset( f,0,sizeof(f) ); f[0]=1; int ans=n;
        for ( int i=1; i<=n; i++ )
        {
            if ( f[a[i]] ) { ans--; continue; }
            for ( int j=a[i]; j<=mx; j++ )
                f[j]|=f[j-a[i]];
        }

        printf( "%d\n",ans );
    }
}