洛谷P5020货币系统

时间:2023-01-16 17:01:02

题目

这个题打眼看上去可能是一个数论或者DP,其实我们可以简化一下题意,即

给定一个集合\(\alpha\),找到几个数使得这几个数可以拼凑起来这个集合里所有的数,且需要使这些数的个数最小。

这样这个题就不难理解了,首先看到数据范围,发现暴搜可以骗不少分,但其实这个题暴搜是可以A的,主要就是可以如何使暴搜的速度加快。

首先我们想如果\(a\)可以被其他数表示出来,且\(a-b\)也可以被其他数表示出来,那\(b\)肯定要在这个集合里,所以我们可以枚举b,然后判断\(a-b\)是否已经被筛过了,但是这样比较慢,可能会T,那正着搜索不行,我们可以考虑反向考虑,因此我们可以用埃拉托色尼筛法的思想,从小到大选择可以满足的数,并在此之前排序一遍,因为如果这个数\(a\)已经被别的数筛去了,\(a\)就不需要再筛其他的数,因为筛掉\(a\)的数,已经把\(a\)能筛掉的数都给筛掉了,因此需要从小到大处理。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[100010], keyi, n;
bool bei[100010];//表示该数能不能被表示出来
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
keyi = 0;
memset(bei, 0, sizeof(bei));
scanf("%d" ,&n);
for (int i = 1; i <= n; i++)
a[i] = read();
sort(a + 1, a + 1 + n);
bei[0] = 1;
for (int i = 1; i <= n; i++)
if (!bei[a[i]])//这个数没有被筛去
{
keyi++;
for (int j = 0; j <= 25010; j ++)
if (bei[j])
bei[j + a[i]] = 1;
}
printf("%d\n", keyi);
}
return 0;
}