d119

輸入說明 ：

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

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

輸出說明 ：

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

這題是DP的問題,也就是動態規劃, 假設現在要用(1,5,10,)來湊47塊

我們先找不用10元,只用1和5來組成47有幾種可能,

再來找用1個10元,和只用(1,5)元組成37(47-10)元有多少可能,

再來找用2個10元和只用(1,5)元組成27(47-20)有多少可能,

再來找用3個10元和只用(1,5)元組成17(47-30)有多少可能,

再來找用4個10元和只用(1,5)元組成7(47-40)有多少可能,

回來看不用10元,只用1和5來組成47有幾種可能

又分成不用5元,只用1元組成

和用1個5元,其他用1元

和用2個5元,其他用1元.....................

現在有10種硬幣,最大的可能是50000

所以我們開一個2維陣列,紀錄1~50000只用某幾種硬幣的可能性

例如(5,1000)

就是用1,5,10,20,50組成1000的可能性有多少種

要算出每一個的做法就是先把上一層的數字加下來,例如(5,1000),一開始先把(4,1000)的結果加進來,代表不用50,只用1,5,10,20組成1000的可能有多少種,

再來去算

我用1個50,和只用1,5,10,20組成1000的可能有多少 . . . . 做到50能用的數量最多,也就是20個

這個表建完了以後,之後只要查最後一層,就可以了

這題的輸入我是用sscanf來做,sscanf詳細的用法看這篇

#include<stdio.h>
#include<string.h>
#define SIZE 50001
long long int table[10][SIZE] = { 0 };
int main()
{   

    int dollar[10] = {1,5,10,20,50,100,200,500,1000,2000};
    int i,j;

    for(i=1;i<SIZE;i++)
        table[0][i]=1;

    for(i=1;i<10;i++)
        for(j=1;j<SIZE;j++)
        {    
            int jtemp=j;
            table[i][j]+=table[i-1][j];

            while(0<=jtemp)
            {
                jtemp-=dollar[i];
                if(jtemp < 0) break;
                if(jtemp==0)
                {    
                    table[i][j]+=1;
                    break;
                }

                table[i][j]+=table[i-1][jtemp];
            }
        }

    char fake_buffer[1000];
    while(gets(fake_buffer))
    {
        int temp,sum=0;
        char *p=fake_buffer;
        int l;
        while(sscanf(p,"%d%n",&temp,&l)==1)
            {
                sum+=temp;
                p+=l;
            }
        if(!sum) break;
        printf("%lld\n",table[9][sum]-1);
    }
    return 0;
}