// 题意 给定一个数p，要求用四种币值为1，5，10，25的硬币拼成p，并且硬币数要最多，如果无解输出"Charlie cannot buy 
coffee."，1<=p<=1万，1<=硬币数量<=1万
// 多重背包 
// 网上见有用完全背包  貌似那个也可以 而且要快些
// 一下是完全背包大致写法
 for (i = 1; i <= 4; ++i) {  

• memset(used,0,sizeof(used));
• for (j = mon[i]; j <= p; ++j)
• if (dp[j-mon[i]] + 1 > dp[j] && dp[j-mon[i]]
• && used[j-mon[i]] + 1 <= num[i]) {
• dp[j]   = dp[j-mon[i]] + 1;
• used[j] = used[j-mon[i]] + 1;
• path[j] = j - mon[i];
• }
• }

#include <iostream>

#include <algorithm>

#include <queue>

#include <math.h>

#include <stdio.h>

#include <string.h>

using namespace std;

#define MOD 1000000007

#define maxn 10010

int dp[maxn];

struct node{

    int from;

    int kind;

    int num;

}rc[maxn];

int main()

{

    int P;

    int C[];

    int V[]={,,,};

    while(scanf("%d %d %d %d %d",&P,&C[],&C[],&C[],&C[]),P|C[]|C[]|C[]|C[]){// 坑爹开始忘记把P加入进行|了

      //  if(P==0) { printf("Charlie cannot buy coffee.\n");continue;}

        memset(dp,,sizeof(dp));

        int ans[]={,,,};

        int i,j,k;

        int tp;

        dp[]=;

        for(i=;i<;i++){

            k=;

            while(C[i]>=k){

                 tp=k*V[i];

                for(j=P;j>=tp;j--)

                    if(dp[j-tp]&&dp[j]<dp[j-tp]+k)

                    {

                        dp[j]=dp[j-tp]+k;

                        rc[j].from=j-tp;

                        rc[j].kind=i;

                        rc[j].num=k;

                    }

                    C[i]-=k;

                    k=k<<;

            }

            if(C[i]){

                    k=C[i];

                tp=k*V[i];

                for(j=P;j>=tp;j--)

                    if(dp[j-tp]&&dp[j]<dp[j-tp]+k)

                    {

                        dp[j]=dp[j-tp]+k;

                        rc[j].from=j-tp;

                        rc[j].kind=i;

                        rc[j].num=k;

                    }

            }

        }

        if(dp[P]){

            j=P;

            while(j){

                ans[rc[j].kind]+=rc[j].num;

                j=rc[j].from;

            }

         printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[],ans[],ans[],ans[]);

        }

        else

            printf("Charlie cannot buy coffee.\n");

    }

    return ;

}