首页 > 其他 > 详细

【洛谷P5020】货币系统

时间:2018-11-12 17:04:19      阅读:174      评论:0      收藏:0      [点我收藏+]

题目大意:给定 N 个数,求在这 N 个数中至少选出几个数能表示出所有数字,输出最少的个数。

题解:由于只有小的数字可以表示大的数字,因此首先需要对这 N 个数字进行从小到大排序。排序之后就变成一道不定个数的数字组合问题,即:完全背包思想。遍历每一个数字,若该数字不能由之前的数字表示出来,则将答案加一,并将这个数字能够表示的数字进行记录即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
const int maxv=25010;

int n,ans,a[maxn];
bool f[maxv];

void read_and_parse(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
}

void solve(){
    for(int i=1;i<=n;i++)if(!f[a[i]]){
        ++ans,f[a[i]]=1;
        for(int j=a[i];j<=a[n];j++)f[j]|=f[j-a[i]];
    }
    printf("%d\n",ans);
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(f,0,sizeof(f));
        memset(a,0,sizeof(a));
        ans=0;
        read_and_parse();
        solve();
    }
    return 0;
}

【洛谷P5020】货币系统

原文:https://www.cnblogs.com/wzj-xhjbk/p/9946963.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!