[NOIP 2018 提高组] 货币系统（数学，dp）

新的学期开始了，是时候好好学习了。每天早上早早起来算法题，何尝不是一件美逝事。

今天看一道很简单的题！一道和数学有关的题，此类题往往需要某种数学证明，一旦数学上没问题，就只是代码实现的问题了。来看题吧：

题目背景

NOIP2018 提高组 D1T2

题目描述

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

输入格式

输入文件的第一行包含一个整数 T，表示数据的组数。

接下来按照如下格式分别给出 T 组数据。 每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。

输入输出样例 #1

输入 #1

2
4
3 19 10 6
5
11 29 13 19 17

输出 #1

2
5

说明/提示

在第一组数据中，货币系统 $(2, [3,10])和给出的货币系统和给出的货币系统(n, a)等价，并可以验证不存在等价，并可以验证不存在m < 2的等价的货币系统，因此答案为的等价的货币系统，因此答案为2。在第二组数据中，可以验证不存在。在第二组数据中，可以验证不存在m < n的等价的货币系统，因此答案为的等价的货币系统，因此答案为5$。

【数据范围与约定】

对于 $100%$ 的数据，满足 $1 ≤ T ≤ 20, n,a[i] ≥ 1$。

题解

题意

题目给了一系列数字$a1,a2,a3….an$，我们要让这些数字的数目尽可能小而能表示的货币数值不变。

思考

这里我必须要提到线性代数/高等代数（线性代数nb！）对于某个数$x$可以由$ti*ai$求和得到，则称$x$可以由$a$线性表示，这个表示它的计算过程称之为线性变换。

那么对于题目给的一系列数字，假如这些数字中有数字能够由其它数字线性表示，那我们就可以认为这个数字是多余的（别人就可以发挥你的作用，你可以被替代了！）。那么我们要找的答案不就是题目给的数组中不能被其他数字线性表示的数字的数量！

实际上我觉得可以这样想，题目给了一个一维向量组，我们要求这个向量组的秩。向量组的秩是向量组的极大无关组的向量的个数（在最小生成树中提到过），也就是那些无法被线性表示的数字的个数。

算法实现

在数学上我们已经完胜了，那么怎么用算法实现求秩呢。我们当然不会真的造一个矩阵求秩，我们只要找出有多少的数字可以被线性表示就可以了。

这里的数只能被小于自己的数字线性表示，那么先对数组$a$排序，用一个数组$f$记录数字能否被线性表示出来。那么通过递推，动态规划，就可得出我们需要的数字范围内的线性表示情况。状态转移：

$f[j] = f[j] | f[j-a[i]]$

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t ;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		int a[25005];
		for(int i=1;i<=n;++i) cin >>a[i];
		int res = n;
		sort(a+1, a+1+n);
		bool f[25005] = {false};
		f[0] = true;
		for(int i=1;i<=n;++i){
			if(f[a[i]]) res--;
			for(int j=a[i];j<=a[n];++j){
				f[j] = f[j] | f[j-a[i]];
			}
		}
		cout << res << "\n";
	}
	return 0;
}