C++将任意给定的整百元钞票，兑换成10元、20元、50元小钞票形式。输出兑换方案总数。 输入 需要兑换的钞票总数n，注意n是整百元钞票，且100<=n<=100000。 输出 输出方案总数。

#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;
}

相关问题

c++怎么解决最少钞票问题

在C++中，解决“最少钞票”问题通常涉及动态规划算法，也称为找零钱问题。这个问题的目标是最小化给出一定金额时所需的最小面额货币组合。例如，给定有5元、10元和20元的硬币，如何用最少的硬币凑出100元。

下面是一个简单的步骤：

1. 定义一个二维数组dp，其中`dp[i]`表示找到总金额i所需的最小硬币数。初始化所有dp值为无限大（如int类型的max_value），除了dp[0]设置为0，因为不需要任何硬币来凑零元。

2. 遍历从1到目标金额的所有整数i。对于每个i，检查是否有可用的硬币j（如5、10、20元等），然后更新dp[i]，如果加上当前硬币的数量小于等于dp[i-j]+1（即当前方案加一个j元硬币比上一个更优），则更新dp[i]为这个更小的结果。

3. 最终，dp[target_amount]就是所需的最小硬币数。遍历dp数组，找出能到达target_amount的那个状态对应的最小硬币数。

#include <iostream>
#include <vector>
using namespace std;

int minCoins(int coins[], int m, int target) {
    vector<int> dp(target + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 1; i <= target; ++i) {
        for (int j = 0; j < m && coins[j] <= i; ++j) {
            if (dp[i-coins[j]] != INT_MAX)
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        }
    }

    return dp[target] == INT_MAX ? -1 : dp[target]; // 返回-1表示无法凑够目标金额
}

// 测试示例
int main() {
    int coins[] = {5, 10, 20};
    int m = sizeof(coins)/sizeof(coins[0]);
    int target = 100;
    cout << "Minimum number of coins: " << minCoins(coins, m, target) << endl;
    return 0;
}

这天,托米家的电影院门口排起了长队--因为最新的电影"托米历险记"就要上映了! 每个人都有且仅有一张面值为25或50或100元的钞票.一张电影票的价格是25元. 托米想知道售票员能否在初始金钱为0并且按排队顺序售票的情况下完成找零.

这个情景描述的是一个经典的动态规划（Dynamic Programming）问题，通常称为“硬币找零”（Coin Change Problem）。在这个问题中，你需要确定给定一组面额的硬币和一个总金额，是否能够组合使用这些硬币来支付指定的费用，同时确保售票员在每个顾客购票时都能提供足够的找零。

为了判断售票员能否完成找零，我们可以使用一个布尔数组 `canChange`，其中 `canChange[i]` 表示用现有的硬币能否凑成 i 元的零钱。初始化所有 `canChange[0...25]` 为 `true`，因为没有需求时，0元是可以的。

然后从最小面额开始（25元），遍历每位顾客，对于每位顾客，如果他们有100元、50元或25元的钞票，我们检查 `canChange[i - coinValue]` 是否为真（coinValue是当前顾客的钞票面额）。如果是，则表示可以用他们的钞票凑出所需的找零，更新 `canChange[i]` 为 true。

下面是简单的 C++ 代码实现：

#include <vector>

bool canMakeChange(int coins[], int n, int amount) {
    std::vector<bool> canChange(amount + 1, false);
    canChange[0] = true;

    for (int i = 0; i < n; ++i) {
        for (int j = coins[i]; j <= amount; ++j) {
            if (canChange[j - coins[i]]) {
                canChange[j] = true;
            }
        }
    }

    return canChange[amount];
}

// 使用
const int coinValues[] = {25, 50, 100}; // 托米家的钞票面额
int main() {
    int numCoins = sizeof(coinValues) / sizeof(coinValues[0]);
    int movieTicketPrice = 25;
    bool canFinish = canMakeChange(coinValues, numCoins, movieTicketPrice);

    if (canFinish) {
        std::cout << "售票员可以完成找零.\n";
    } else {
        std::cout << "售票员无法完成找零.\n";
    }

    return 0;
}