本文共 830 字,大约阅读时间需要 2 分钟。
题目链接:
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld现有N元钱,兑换成小额的零钱,有多少种换法?币值包括1 2 5分,1 2 5角,1 2 5 10 20 50 100元。
(由于结果可能会很大,输出Mod 10^9 + 7的结果)第一行输入一个整数T,代表有T组数据
接下来T行,每行输入1个数N,N = 100表示1元钱。(1 <= N <= 100000)输出Mod 10^9 + 7的结果
2
5 4
4
3
5分钱兑换为零钱,有以下4种换法:
1、5个1分 2、1个2分3个1分 3、2个2分1个1分 4、1个5分
类似于完全背包,好像是母函数,推出公式就行了。
#includeusing namespace std;const int MOD = 1E9 + 7;int t, n, dp[100005];int m[] = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < 13; i++) for (int j = m[i]; j <= n; j++) dp[j] = (dp[j] + dp[j - m[i]]) % MOD; printf("%d\n", dp[n]); } return 0;}
转载地址:http://emftf.baihongyu.com/