题目

题意简化一下就是找题目给定的n个数最多能消掉多少个，我们用个tong[i]来记录i这个数值能不能用小于等于i的货币组合起来，等于1意味着他只能由自己本身的货币组成，等于2说明他可以被其他货币组成（此时的数不一定是货币，但等于2的货币不能要），最后只需要统计一下n个数里有几个tong等于1即可，然后对于每个tong等于1或2的数，都可以跟另外一个tong等于1或2的数组合起来，又可以递推求解tong数组了

//long long，inline后加函数类型

//关键字：y1,time,tm,end,next,hash, j0,j1,jn,y0,yn,_end会re;

#include <bits/stdc++.h>

#define N 1001001

using namespace std;

int a[N], dp[N], tong[N];

int main()

{

 	int T;

// 	freopen("ha.txt", "w", stdout);

 	scanf ("%d", &T);

 	while (T--)

 	{

	 	int n, ans = 0;

	 	memset(tong, 0, sizeof(tong));

	 	memset(dp, 0, sizeof(dp));

	 	scanf("%d", &n);

	 	for (int i = 1; i <= n; i++)

	 		scanf("%d", &a[i]), tong[a[i]] = 1;//tong代表此数已经可以被消掉.

	 	sort(a + 1, a + 1 + n);

	 	for (int i = 1; i <= n; i++)

	 	{

	 		if (tong[a[i]] != 2)

			 	ans++;

	 		for (int j = 1; j <= 25000; j++)

	 		{

	 			if (tong[j] == 1 || tong[j] == 2)//j可以被表示出来

	 			tong[a[i] + j] = 2;

			}

	 	}

	 	printf("%d\n", ans);

 	}

 	return 0;

}