目录
链接
博客链接
题目链接
题目内容
题目描述
题目大意
格式
输入
输出
数据
样例
输入
输出
解释
数据范围
提示
题解

题目名称：货币系统

来源：2018年NOIP提高组

链接

博客链接

CSDN
洛谷博客
洛谷题解

题目链接

LibreOJ(2951)
洛谷(P5020)
大视野在线评测(1425)

题目内容

题目描述

在网友的国度中共有\(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\)。

提示

因为钱掉进了水里，所以这是一道水题。

题解

输入每种面额后，先将其从小到大排序。

引理

如果一个面额无法被比它小的面额凑出来，那么必须选，否则一定不选。

证明：前者很显然，因为这个数不可能被比其更大的数凑出来。

后者，因为这个数可以被其他数凑出来，那么需要这个数组成的数只需要凑成这个数的数就可以了。

于是我们按顺序做完全背包，如果发现没被前面的数背包得到就选，否则不选。

graph TD
A(开始处理)-->B[是否被背包得到]
B-->|是|C[弃置]
B-->|否|D[选择该元素]
D-->E[在原来的基础上用该元素进行完全背包]
C-->F(进入下一次处理)
E-->F

//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;

}

[NOIP提高组2018]货币系统的相关教程结束。