[TOC]
题目名称：货币系统
来源：2018年NOIP提高组
在网友的国度中共有$n$种不同面额的货币，第$i$种货币的面额为$a[i]$，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为$n$、面额数组为$a[1..n]$ 的货币系统记作$(n,a)$。
在一个完善的货币系统中，每一个非负整数的金额$x$都应该可以被表示出，即对每一个非负整数$x$，都存在$n$个非负整数$t[i]$满足$a[i] \times t[i]$的和为$x$。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额$x$不能被该货币系统表示出。例如在货币系统$n=3$，$a=[2,5,9]$中，金额$1,3$就无法被表示出来。
两个货币系统$(n,a)$ 和$(m,b)$ 是等价的，当且仅当对于任意非负整数$x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 现在网友们打算简化一下货币系统。他们希望找到一个货币系统$(m,b)$ ，满足$(m,b)$ 与原来的货币系统$(n,a)$ 等价，且$m$尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的$m$。
已知货币系统$(n,a)$，$n$表示有多少种面额，$a$是一个集合，各个元素表示各种面额的大小。
两个货币系统$(n,a)$ 和$(m,b)$是等价的，当且仅当对于任意非负整数$x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
找到一个货币系统$(m,b)$ ，满足$(m,b)$ 与原来的货币系统$(n,a)$ 等价，且$m$尽可能的小。其中 \(b\in a\)。
输入文件的第一行包含一个整数$T$，表示数据的组数。
接下来按照如下格式分别给出$T$组数据。 每组数据的第一行包含一个正整数$n$。接下来一行包含$n$个由空格隔开的正整数$a[i]$。
输出文件共有$T$行，对于每组数据，输出一行一个正整数，表示所有与 \((n,a)\) 等价的货币系统 \((m,b)\) 中，最小的 \(m\)。
2
4
3 19 10 6
5
11 29 13 19 17
2
5
在第一组数据中，货币系统$(2,[3,10])$ 和给出的货币系统$(n,a)$ 等价，并可以验证不存在$m<2$ 的等价的货币系统，因此答案为$2$。 在第二组数据中，可以验证不存在$m<n $的等价的货币系统，因此答案为$5$。
| 测试点 | n | a[i] | 测试点 | n | a[i] |
| 1 | =2 | ≤10000 | 11 | ≤13 | ≤16 |
|---|---|---|---|---|---|
| 2 | 12 | ||||
| 3 | 13 | ||||
| 4 | =3 | 14 | ≤25 | ≤40 | |
| 5 | 15 | ||||
| 6 | 16 | ||||
| 7 | =4 | 17 | ≤100 | ≤25000 | |
| 8 | 18 | ||||
| 9 | =5 | 19 | |||
| 10 | 20 |
对于$100%$的数据，满足$1≤T≤20,n,a[i]≥1$。
因为钱掉进了水里，所以这是一道水题。
输入每种面额后，先将其从小到大排序。
引理
如果一个面额无法被比它小的面额凑出来，那么必须选，否则一定不选。
证明：前者很显然，因为这个数不可能被比其更大的数凑出来。
后者，因为这个数可以被其他数凑出来，那么需要这个数组成的数只需要凑成这个数的数就可以了。
于是我们按顺序做完全背包，如果发现没被前面的数背包得到就选，否则不选。
//C++
#include<bits/locale_facets.h>
#include<memory.h>
#include<stdio.h>
using namespace std;
inline void output(long long value);
inline long long input();
short a[101],able[25001];
int main()
{
short T=input();
while(T--)
{
short n=input(),maximum=0;
short must=n;
for(short i=1;i<=n;i++)maximum=max(maximum,a[i]=input());
able[0]=true;
for(short i=1;i<=n;i++)
for(short j=a[i];j<=maximum;j++)
if(able[j-a[i]])able[j]++;
for(short i=1;i<=n;i++)
if(able[a[i]]>1)must--;
memset(able,0,50002);
output(must),putchar(‘\n‘);
}
return 0;
}
inline void output(long long o)
{
if(o<0)putchar(‘-‘),o=-o;
if(o>=10)output(o/10);
putchar(o%10^‘0‘);
}
inline long long input()
{
bool positive=true;
char now=getchar();
long long i=0;
for(;!isdigit(now);now=getchar())
if(now==‘-‘)positive=!positive;
for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^‘0‘);
return positive?i:-i;
}
原文：https://www.cnblogs.com/Alvin-Tree/p/11561879.html