d655 - 許胖公仔
題目描述
題目要求計算給定金額 N 所需的最少硬幣數量。硬幣面額包括 1, 5, 10, 50, 100, 500, 1000, 30, 70, 110。
解題思路
此題可以使用貪心演算法，但由於硬幣面額的特殊性（包含 30, 70, 110），單純的貪心策略可能無法得到最佳解。程式碼中使用了動態規劃的思想，預先計算了 dp[i] 表示金額 i 所需的最少硬幣數量，其中 i 的範圍是 0 到 1000。對於輸入金額 a，程式碼將其分解為 a / 1000 和 a % 1000 兩部分，分別計算千元位和百元位以下所需的最少硬幣數量，然後將兩者相加。dp 陣列的預計算避免了每次計算時重複計算較小金額的最少硬幣數量，提高了效率。
複雜度分析
- 時間複雜度: O(1000 + T)，其中 T 是輸入的 case 數量。預計算
dp陣列需要 O(1000) 的時間，處理每個 case 需要 O(1) 的時間。 - 空間複雜度: O(1001)，用於儲存
dp陣列。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int dp[1001]={0,1,2,3,4,1,2,3,4,5,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,3,4,5,6,7,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,3,4,5,6,7,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,3,4,5,6,7,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,3,4,5,6,7,3,4,5,6,7,4,5,6,7,8,1,2,3,4,5,2,3,4,5,6,1,2,3,4,5,2,3,4,5,6,2,3,4,5,6,3,4,5,6,7,2,3,4,5,6,3,4,5,6,7,2,3,4,5,6,3,4,5,6,7,2,3,4,5,6,3,4,5,6,7,2,3,4,5,6,3,4,5,6,7,3,4,5,6,7,4,5,6,7,8,2,3,4,5,6,3,4,5,6,7,2,3,4,5,6,3,4,5,6,7,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,3,4,5,6,7,4,5,6,7,8,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,4,5,6,7,8,5,6,7,8,9,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,10,5,6,7,8,9,6,7,8,9,1