题解 | #兑换零钱#

兑换零钱

https://www.nowcoder.com/practice/67b93e5d5b85442eb950b89c8b77bc72

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 10010;
int f[N], a[N];

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = a[i]; j <= m; j ++)
            f[j] = min(f[j], f[j - a[i]] + 1);
    if(f[m] > 5000) cout << "-1" << endl;
    else cout << f[m] << endl;
    return 0;
}

全部评论

相关推荐

点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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