货币系统

题意：有n种货币，每一种货币面值为a[i]，并且每种货币有无穷个，请问只需多少种货币可以达到和这n种货币一样的支付范围？

思路：多重dp，将a数组按升序排列，如果第i种货币的值可以被前i-1种货币组成，则该面值的货币可以不要，计算不能被组成的货币种类数即可。

代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define inf 1000000007

int a[2005], dp[30000];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int z=0;
        sort(a+1,a+n+1);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(dp[a[i]]==1)
            {
                continue;
            }
            z++;
            for(int j=0;j<=25000;j++)
            {
                if(j>=a[i])
                dp[j]=dp[j]|dp[j-a[i]];
            }
        }
        cout << z << endl;
    }
    return 0;
}