货币系统

货币系统

https://ac.nowcoder.com/acm/problem/21228

题意:有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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:31
点赞 评论 收藏
分享
牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
水墨不写bug:疑似没有上过大学
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务