d119: 有獎徵答：換零錢

內容

LuLu 在家無聊看電視，突然轉到一台有獎徵答，CallIn 進去答對者可以得到大筆金額，

但答錯了又浪費打電話的錢，所以 LuLu 想請你寫一個程式，幫他拿到大筆金額。

有獎徵答內容：

若給你２枚１０元硬幣，要你算出還有多少種排列組合之總數相同（不包含２枚１０元這組）？

(2/2 9:00 加強測試資料、重新整理題目內容)

輸入

有多組測試資料，每組測試資料佔一行，每行會有 m 個以空白分開的正整數，
若該組測試資料只有 0，請不要對此輸出任何數字。

(每行的總金額不會超過 50000，且數字可為 1,5,10,20,50,100,200,500,1000,2000)

範例:

給了 10,10，所以要算出總數為 20 的所有組合總數(不包含 10,10)。

1
5
10
20
50
100
200
500
1000
2000
1000 1000
1000 500 200 200 100
0

輸出

對每一組測試資料輸出有多少種用"1,5,10,20,50,100,200,500,1000,2000"所排列的組合(不包含輸入的組合)。

範例:

所有組合總數為 20 的排法有:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 5 1 1 1 1 1 1 1 1 1 1
5 5 5 1 1 1 1 1
5 5 5 5
10 1 1 1 1 1 1 1 1 1 1
5 10 1 1 1 1 1
5 5 10
20

共 9 種(不包含 10 10)

所以輸出 9。

0
1
3
9
56
343
3274
135816
3995278
193386179
193386179
193386179

解題思路

經典的背包問題，用 DP 列出所有金額的可能性，而根據題意，輸入最大值為 50000，所以理論上要建一個大小為 50000 的表。

由於 1 在做 DP 時又是特別的存在 ，所以不用將 1 列熱考慮，排出 1 之後，會發現剩下的硬幣皆為 5 的倍數，而這種情況下 DP 表會變成固定每 5 個元素才改變一次，如下表

{ 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6….. }

而既然知道元素每 5 個一循環的改變那就沒必要算重複出現的元素，將硬幣同除 5 變成

money[] = { 1, 2, 4, 10, 20, 40, 100, 200, 400 }

這時候再建表會就會變成下表

{ 1, 2, 4, 6, 10, 14… }

如此把沒有意義的元素過濾掉，表的大小需求就能從 50000 降至 10000。

因為硬幣被同除 5 了，所以要將輸入除以 5 後查表，再將得到的值減 1 (題意"不包含輸入組合")輸出。

完整程式碼

AC (3ms, 160KB)

#include <stdio.h>
#define MAX 10001

const int money[] = { 1, 2, 4, 10, 20, 40, 100, 200, 400 };
unsigned long long list[MAX];
int n, tmp;
char input[1000], * st;

inline char* getUInt(unsigned int* dst, char src[])
{
    while (*src < '0')
        if (!*src++) return NULL;
    *dst = *src ^ '0';
    while (*++src >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (*src ^ '0');
    return src;
}

int main()
{
    for (int i = 0; i < MAX; i++)
        list[i] = 1;
    for (int i = 0; i < 9; i++)
    {
        for (int j = money[i]; j < MAX; j++)
            list[j] += list[j - money[i]];
    }
    while (gets(input) && input[0] - '0')
    {
        n = 0, st = input;
        while (st = getUInt(&tmp, st))
            n += tmp;
        printf("%llu\n", list[n / 5] - 1);
    }
    return 0;
}