HDU 2069 Coin Change

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//dp[i],最多100枚硬币
const int a[5] = {1, 5, 10, 25, 50};
int main() {
    int n;
    while (cin >> n) {
        ll dp[255][101];  // dp[j][k]:用k个硬币组成j值的个数
        dp[0][0] = 1;
        for (int i = 0; i < 5; i++)
            for (int k = 1; k <= 100; k++)  // k个硬币
                for (int j = a[i]; j <= n; j++) dp[j][k] += dp[j - a[i]][k - 1];
        ll ans = 0;
        for (int i = 0; i <= 100; i++) ans += dp[n][i];
        cout << ans << endl;
    }
    return 0;
}

母函数/完全背包 待了解

算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

07-18 14:34
门头沟学院 Java
感觉招聘要求好高,这都是招什么人才
电气电子小朋友:你都说了这是大疆,无人机顶级企业,薪资30k-50k,要求高是正常的
点赞 评论 收藏
分享
06-26 15:33
青岛工学院 Java
积极的秋田犬要冲国企:他现在邀请我明天面试
点赞 评论 收藏
分享
想按时下班的大菠萝在...:隔壁学校的,加油多投, 实在不好找可以下个学期开学找,把算法八股准备好,项目有空再换换
投了多少份简历才上岸
点赞 评论 收藏
分享
有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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