HDU2069

/*!!!硬币总数不能超过100个!!!*/
#include <iostream>
#include<cstdio>
#include<cstring>
#define M 250
#define N 100
using namespace std;
int dis[5]={1,5,10,25,50};
int c1[M+1][N+1],c2[M+1][N+1];
//开个二维数组用来控制硬币总数
void solve()
{
    int i,j,k,l;
    for(i=0;i<=100;i++)
    c1[i][i]=1;
    for(i=1;i<5;++i)
    {
        for(j=0;j<=M;++j)
        {
            for(k=0;k+j<=M;k+=dis[i])
            {
                for(l=0;l+k/dis[i]<=100;++l)
                     c2[k+j][l+k/dis[i]]+=c1[j][l];
            }
        }
        for(j=0;j<=M;++j)
        {
            for(l=0;l<=100;++l)
            {
            c1[j][l]=c2[j][l];
            c2[j][l]=0;
            }
        }
    }
}
int main()
{
    int i,l,n;
    solve();
//     freopen("xx.out","w",stdout);
//    for(i=0;i<=250;++i)
//    {
//        int sum=0;
//        for(l=0;l<=100;++l)
//        sum+=c1[i][l];
//        printf("%d = %d\n",i,sum);
//    }
    while(scanf("%d",&n)!=EOF)
    {
        int sum=0;
        for(i=0;i<=100;++i)
        sum+=c1[n][i];
        printf("%d\n",sum);
    }
//    cout << "Hello world!" << endl;
    return 0;
}