题目描述：
给出 $n$ 种货币，第 $i$ 种为 $a[i]$ ，假设每一种都有无穷多张。找到这 $n$ 张中最小的 $m$ ，满足这 $m$ 张可以表出其他所有的。
数据范围：
$1\le n \le 100,1 \le a[i] \le 25000$
题解：
类似极大线性无关组，线性基。但是这个需要满足系数是非负的。如果系数可以任意，那么一张足够。系数需要满足非负，类似完全背包，需要看后面的能不能用前面的表示出来，也就是能不能装满。使用 $dp[i]$ 表示能否表出，那么
就是完全背包的一维形式，注意初始条件， $dp[0] = 1$ 。因为 $0$ 只有一种方法，那就是所有的都不用。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 3e4 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
bool dp[maxn];
void solve()
{
memset(dp, false, sizeof(dp));
sort(a, a + n);
dp[0] = true;
int ans = 0;
for (int i = 0; i < n; ++i)
{
if (dp[a[i]] == true)
continue;
++ans;
for (int j = a[i]; j <= a[n - 1]; ++j)
{
dp[j] |= dp[j - a[i]];
}
}
cout << ans << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int tcase;
read(tcase);
while (tcase--)
{
read(n);
for (int i = 0; i < n; ++i)
read(a[i]);
solve();
}
return 0;
}
|