题目描述
新西兰货币包含以下面值的纸币和硬币：
- 纸币：
$100、$50、$20、$10、$5 - 硬币：
$2、$1、50c、20c、10c、5c
题目要求：给定一个金额（以美元为单位，保证是5c的整数倍），计算该金额可以由这些面值组合成的不同方式数量。顺序不同不算不同方式。例如20c有以下四种组合方式：
1 × 20c2 × 10c10c + 2 × 5c4 × 5c
输入格式
- 输入包含多行，每行一个实数，表示金额，不超过
$300.00。 - 每个金额保证是
5c的整数倍。 - 输入以一行
0.00结束。
输出格式
- 每个金额输出一行，包含金额（保留两位小数，右对齐，宽度为6 66）和组合方式数量（右对齐，宽度为17 1717）。
示例输入
0.20 2.00 0.00示例输出
0.20 4 2.00 293问题分析
这是一个典型的完全背包计数问题。我们需要计算用给定面值的硬币组成目标金额的不同组合数，且不考虑顺序。
为了方便计算，我们可以将金额统一转换为分（cents \texttt{cents}cents）为单位。因为所有面值都是5c的整数倍，因此可以将金额除以5 55来简化问题规模。
转换面值
转换后的面值（以5c为单位）：
| 原面值 | 转换后（单位：5c） |
|---|---|
5c | 1 |
10c | 2 |
20c | 4 |
50c | 10 |
$1 | 20 |
$2 | 40 |
$5 | 100 |
$10 | 200 |
$20 | 400 |
$50 | 1000 |
$100 | 2000 |
这样，问题转化为：用上述11 1111种面值（单位是5c），组成目标金额n nn（已除以5 55）的不同方式数。
动态规划设计
设d p [ i ] dp[i]dp[i]表示组成金额i ii的组合方式数量。
初始状态：d p [ 0 ] = 1 dp[0] = 1dp[0]=1（什么也不取算一种方式）。
状态转移方程：
对于每种面值c cc，遍历j jj从c cc到最大金额：
d p [ j ] + = d p [ j − c ] dp[j] += dp[j - c]dp[j]+=dp[j−c]
该方程表示：若我们使用一个面值为c cc的硬币，则剩余金额为j − c j-cj−c，其组合数为d p [ j − c ] dp[j-c]dp[j−c]，累加到当前d p [ j ] dp[j]dp[j]中。
算法步骤
- 将金额转换为整数（分），再除以5 55得到目标值t a r g e t targettarget。
- 使用动态规划预处理出所有可能金额（最大为300.00 300.00300.00，即6000 60006000个
5c单位）的组合数。 - 对每个输入金额，直接查表输出。
代码实现
// Dollars// UVa ID: 147// Verdict: Accepted// Submission Date: 2016-01-22// UVa Run Time: 0.012s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net//// PDF 格式的试题描述和 UVa 网页上的试题描述有出入，主要是上限提高到 300 美元。输出格式亦有改变。#include<bits/stdc++.h>usingnamespacestd;longlongintcache[6001]={0};voidinitialize(){// 面值以 5c 为单位intcoins[11]={1,2,4,10,20,40,100,200,400,1000,2000};cache[0]=1;for(inti=0;i<11;i++)for(intj=1;j<6001;j++)if(j-coins[i]>=0)cache[j]+=cache[j-coins[i]];}intmain(intargc,char*argv[]){initialize();string line;while(cin>>line){string backup=line;line.erase(line.find('.'),1);// 去掉小数点istringstreamiss(line);intmoney;// 单位：分iss>>money;if(money==0)break;// 输出格式：金额右对齐宽度6，组合数右对齐宽度17cout<<fixed<<setprecision(2)<<setw(6)<<right<<backup;cout<<setw(17)<<right<<cache[money/5]<<endl;}return0;}复杂度分析
- 预处理：O ( 11 × 6000 ) ≈ 66000 O(11 \times 6000) \approx 66000O(11×6000)≈66000次操作，可忽略不计。
- 查询：O ( 1 ) O(1)O(1)。
- 空间复杂度：O ( 6000 ) O(6000)O(6000)。
总结
本题是完全背包计数问题的典型应用，通过金额单位归一化（除以5c）简化了计算，利用动态规划预处理所有可能金额的组合数，实现了高效查询。注意输入金额需要正确处理为整数形式，并满足输出格式要求。
