小明有n张50元的钞票,他想去银行换成一元、五元和十元的零钱,每种零钱至少3张,问一共有多少种兑换方案?C++代码
时间: 2024-02-12 17:05:41 浏览: 261
好的,以下是对应的C++代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 205;
int dp[MAXN][MAXN];
int main() {
int n;
cin >> n;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= 3; i++) {
for (int j = i * 10; j <= n * 50; j++) {
for (int k = 1; k <= min(j / 10, 50); k++) {
dp[i][j] += dp[i - 1][j - k * 10];
}
}
}
cout << dp[3][n * 50] << endl;
return 0;
}
```
其中,我们可以发现题目中给出的条件是每种零钱至少3张,因此我们可以将零钱面额限制在1元、5元、10元,并且每种面额最多使用50张。然后,我们可以定义状态dp[i][j]表示前i种面额,一共j元的兑换方案数。最终答案即为dp[3][n * 50]。
接着,我们可以根据上述状态转移方程,使用三重循环进行状态转移,得到最终的结果。
需要注意的是,由于每种面额最多使用50张,因此我们在第二重循环中枚举的数值应该是i * 10到n * 50。在第三重循环中,我们需要限制每种面额最多使用50张,因此我们枚举的数值应该是1到min(j / 10, 50)。
希望能够帮到你!
阅读全文