#include <iostream> using namespace std; int main() { int n; cin >> n; int dp[4][n/10+1]; int c[4] = {0, 10, 20, 50}; // 面额列表 // 初始化 for (int i = 0; i <= n/10; i++) { dp[1][i] = 1; } for (int i = 2; i <= 3; i++) { for (int j = 0; j <= n/10; j++) { dp[i][j] = 0; } } // 递推 for (int i = 2; i <= 3; i++) { for (int j = 1; j <= n/10; j++) { dp[i][j] = dp[i-1][j]; if (j >= c[i]) { dp[i][j] += dp[i][j-c[i]]; } } } // 输出结果 cout << dp[3][n/10] << endl; return 0; }

这是一个兑换零钱的问题，使用动态规划算法可以解决。其中，dp[i][j] 表示使用前 i 种面额的硬币兑换 j 元钱的方案数。则最终答案为 dp[3][n/10]，其中 3 表示有三种面额的硬币。

初始化 dp 数组，当只使用第一种面额的硬币时，对任意 j，都只有一种兑换方式。即 dp[1][j] = 1。

然后考虑递推公式。假设我们已经求出了 dp[i-1][j]，现在需要求出 dp[i][j]。那么我们可以分为两种情况：

1. 不使用第 i 种面额的硬币。这种情况下，兑换方案数为 dp[i-1][j]。
2. 使用若干枚第 i 种面额的硬币。这种情况下，兑换方案数为 dp[i][j-c[i]]，其中 c[i] 表示第 i 种面额的硬币的面额。

因此，递推公式为：

dp[i][j] = dp[i-1][j] + dp[i][j-c[i]]。

最终的答案为 dp[3][n/10]。

下面是 C++ 代码实现：