洛谷P5020 货币系统

题目

题意简化一下就是找题目给定的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
", ans);
 	}
 	return 0;
}