【每日一题】货币系统

货币系统

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


题意:


给n种货币,每个面值ai​,数量无限,是否能去掉几种货币,使得原本这几种货币能组成的数仍能组成是否能去掉几种货币,问最后最少能剩下多少货币。


思路:


1.打算化简一下货币系统,其实就是去掉几种货币,说明剩下的货币能表示被减去的货币。
2.最小的不能去掉,因为其它的货币表示不了面值最小的货币,但是面值最小的可能表示其它面值的货币。
3.能组成某一种某种值的一定是一种或多种面值比他小的货币共同组成他,一个或多个数的和能组成的数,这不就是01背包。
3.所以接下来就是第二小的货币,如果他是第一小的货币的倍数就不需要,不是就存进背包里。
4.接下来就是第三小的货币,如果他能由前面的货币组成就不需要,不能就存进背包里。
5.继续操作4,最后背包货币的数量就是答案。


Code:


#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int n,a[105],dp[25005];
int main() {
    int t; js;
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        sort(a+1,a+1+n);
        fill(dp,dp+25005,0);
        dp[0]=1;
        int m,ans=0;
        for(int i=1;i<=n;++i) {
            if(!dp[a[i]]) ++ans;
            else continue;
            for(int j=a[i];j<=25000;++j) dp[j] |= dp[j-a[i]];
        }
        cout<<ans<<endl;
    }
}
每日一题 文章被收录于专栏

牛客每日一题

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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