货币系统

货币系统

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;
}
全部评论

相关推荐

昨天 10:56
门头沟学院 Java
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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