51 nod 2464 货币系统

n数据范围100,货币是25000,用背包去处理下每个价格需要几张组成，然后遍历一遍,=1的都是新货币系统的。

#include<bits/stdc++.h>
#define fp(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
typedef double dl;
using namespace std;

const int N=3e5+7;
const ll M=1e9+7;
const int INF=0x3f3f3f3f;

int n,m;
int a[N];
int f[N];
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=N;i++) f[i]=-10000;
    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i];j<=25000;j++)
        {
            f[j]=max(f[j],f[j-a[i]]+1);
        }
    }
    int ans=0;
    for(int i=1;i<=25000;i++)
    {
        if(f[i]==1)    ans++;
    }
    printf("%d\n",ans);


}

int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0),cout.tie(0);
    int T; scanf("%d",&T);
    for(int i=1;i<=T;i++)
        solve();
}