学步园

            这个题和之前的硬币的题是一样的，只不过面值不一样而已，但是这个题写一个dfs会超时。      

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define LL long long
using namespace std;

int coin[]= {1,5,10,25,50};
LL d[30009];
int main()
{
    //freopen("in.txt","r",stdin);
    int money;
    memset(d,0,sizeof(d));
    d[0]=1;
    for(int i=4; i>=0; i--)
    {
        for(int j=1; j<=30000; j++)
        {
            if(j>=coin[i])
                d[j]+=d[j-coin[i]];
        }
    }
    while(scanf("%d",&money)!=EOF)
    {
        if(d[money]>1)
            cout<<"There are "<<d[money]<<" ways to produce "<<money<<" cents change.\n";
        else
            cout<<"There is only 1 way to produce "<<money<<" cents change.\n";
    }
    return 0;
}