题目

这个题打眼看上去可能是一个数论或者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;

}