UVa 674 Coin Change

题目描述

给定555种硬币：505050美分、252525美分、101010美分、555美分和111美分。对于任意金额（单位：美分），求用这些硬币组成该金额的不同方式数（不考虑顺序）。金额最大为748974897489美分。

输入格式

多行输入，每行一个整数，表示金额（单位：美分）。

输出格式

对于每个金额，输出一行整数，表示不同的组成方式数。

样例

输入

11 26

输出

4 13

题目分析

本题是完全背包问题（硬币无限使用）的组合计数，且硬币面额固定。使用动态规划，dp[i][j]表示使用前i种硬币组成金额j的方式数。状态转移为：

• 不使用第i种硬币：dp[i-1][j]
• 使用第i种硬币：dp[i][j - coins[i]]（至少使用一枚）

最终dp[5][j]即为答案。

解题思路

1. 定义硬币面额数组coins[1..5] = {1, 5, 10, 25, 50}。
2. 初始化dp[0][0] = 1，其余为 0。
3. 对每种硬币i从 1 到 5：
   • 对金额j从 0 到MAX：
     • dp[i][j] = dp[i-1][j]（不用该种硬币）
     • 若j >= coins[i]，则dp[i][j] += dp[i][j - coins[i]]（用该种硬币）
4. 查询时直接输出dp[5][cents]。

由于金额最大 7489，使用long long存储结果（数量可能较大）。

复杂度分析

• 预计算：O(5×7490)O(5 \times 7490)O(5×7490)，约3.7×1043.7 \times 10^43.7×104，极快。
• 查询：O(1)O(1)O(1)。

代码实现

// Coin Change// UVa ID: 674// Verdict: Accepted// Submission Date: 2016-08-17// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcoins[6]={0,1,5,10,25,50};longlongintways[6][7500];memset(ways,0,sizeof(ways));ways[0][0]=1;for(inti=1;i<=5;i++)for(intj=0;j<=7489;j++){ways[i][j]=ways[i-1][j];if(j-coins[i]>=0)ways[i][j]+=ways[i][j-coins[i]];}intcents;while(cin>>cents)cout<<ways[5][cents]<<'\n';return0;}

总结

本题是完全背包计数问题的标准解法，通过动态规划递推，以硬币种类为阶段，金额为状态，累加组合数。关键点包括：

• 二维DP\texttt{DP}DP清晰表示状态转移。
• 注意金额为000时有一种方式（什么都不用）。
• 使用long long防止溢出。

该解法是动态规划入门经典题。