一个背包思维题
题目链接
题目思路
对于一个与[n, a]相同的货币系统 如果在a中有可以用其他值表示出来的值 我们就可以将它删去 将所有可以删掉的值删去后我们就可以得到最小的m [m, b]系统
我们可以通过背包来解决这个问题
ac代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25010;
int n;
int a[N], f[N];
void solve()
{
scanf("%d", &n);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
int ans = n;
f[0] = 1;
for (int i = 1; i <= n; i ++ )
{
if (f[a[i]])
{
ans -- ;
continue;
}
for (int j = a[i]; j <= a[n]; j ++ ) f[j] |= f[j - a[i]];
}
printf("%d\n", ans);
}
int main()
{
int t;
scanf("%d", &t);
while (t -- )
{
solve();
}
return 0;
}