2011-06-01 22:50:40Morris
d655. 許胖公仔
http://zerojudge.tw/ShowProblem?problemid=d655
內容 ：
為了讓人民用一枚錢幣就可以買到許胖公仔,呆丸國政府預計會在2199年發行30元,70元,110元的硬幣,
除此之外,他們的原本已有面額1元5元10元50元100元500元1000元的硬幣,
asas,一個普通宅的高中生,他覺得這實在是太愚蠢了,連吃個晚飯都要帶一堆零零散散的硬幣,
但他又必須帶足剛好數目的晚餐錢,免得老闆找錢找了老半天浪費他看動畫的時間,
他決定要在2199年前寫一個程式輸入他當天的晚餐錢,輸出他所需帶的最少錢幣數量,
但他覺得這程式實在是太簡單了,只對難題有興趣的他決定把程式的實作交給你來處理.
輸入說明
：
第一行輸入為一個整數t(1<=t<=1000001)表示要處理的表case數.
每一個case只需輸入一個整數N(0<=N<=2000000000)表他當天的晚餐錢.
每一個case只需輸入一個整數N(0<=N<=2000000000)表他當天的晚餐錢.
輸出說明
：
對於每一個input case請輸出一個整數表他最少需要帶的錢幣總數.
範例輸入 ：
3 30 140 250
範例輸出 ：
1 2 3
提示
：
背景知識：
反證法
TLE的人實在是太愚蠢了
TLE的人實在是太愚蠢了
出處
：
反證法
(管理：pcshic)
不懂什麼是反證法，直覺DP下
/**********************************************************************************/
/* Problem: d655 "許胖公仔" from 反證法 */
/* Language: C */
/* Result: AC (668ms, 256KB) on ZeroJudge */
/* Author: morris1028 at 2011-05-30 21:16:02 */
/**********************************************************************************/
#include<stdio.h>
main() {
int N, a, b, DP[1000] = {}, T;
int money[9] = {30,70,110,1,5,10,50,100,500};
for(a = 0; a < 1000; a++)
for(b = 0; b < 9; b++)
if(a + money[b] < 1000) {
if(DP[a + money[b]] == 0) {
if(a == 0)
DP[a + money[b]] = 1;
else
DP[a + money[b]] = DP[a] + 1;
}
else if(DP[a + money[b]] > DP[a] + 1)
DP[a + money[b]] = DP[a] + 1;
}
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
printf("%d\n", N/1000 + DP[N%1000]);
}
return 0;
}
上一篇：d633. 幼稚王國的麥田圖騰
下一篇：d807. 方方