一道很简单的找钱问题，呜呜呜，蒟蒻不会TOT
前几天去考试，有一道题我挂了{:10_266:}问题是这样的：
我有 n 元钱，我想把它们兑换成面值为 1, 2, 5 的钱，问有多少种方法？1 <= n <= 1e5
输入样例：
输入：5
输出：4
输入：10
输出：10
我直接写了一个斐波那契数列，然后我挂了……原因很简单，有重复的方案……
但是枚举钱数也不对，十的五次啊喂{:10_250:}
唉，我真是个……蒟蒻{:10_243:}
求思路，谢谢大佬们！ @tommyyu @xiaosi4081 @柿子饼同学 @陈尚涵 我**连这道题都不会，脸都丢光了{:10_250:} 本帖最后由 tommyyu 于 2023-1-20 17:33 编辑
思路就是解不定方程，枚举5元钱的个数，再针对每一种情况进行求解，最后相加#include <iostream>
using namespace std;
long long one_and_two_count(int n) {
if(n == 1) return 1;
if(n == 0) return 1;
if(n % 2) return one_and_two_count(n-1);
return n/2+1;
}
int main()
{
int n;
cin >> n;
long long s = 0;
for(int five = 0; five*5 <= n; ++five) {
int one_two = n - 5 * five;
s += one_and_two_count(one_two);
}
cout << s;
return 0;
}
建议如果学有余力可以直接提前学数学，对文化课打比赛都很有帮助（个人建议，未必准确） tommyyu 发表于 2023-1-20 17:30
思路就是解不定方程，枚举5元钱的个数，再针对每一种情况进行求解，最后相加
建议如果学有余力可以直接提 ...
数学真没学好……要是我考试之前补点数学就好了{:10_266:}
页:
[1]