POJ 1787

好像贪心也可以，以后再看看。标程16ms 晕。

//400K    125MS

#include <iostream>
using namespace std;

const int MAX=10001;
typedef struct _node
{
    int c1;
    int c2;
    int c3;
    int c4;
}Node;

Node Dp[MAX];
int value[4]={1,5,10,25};
bool Used[MAX];
int flag;
int N;
int price;
int left_count;

int main()
{
    while(cin>>N>>Dp[0].c1>>Dp[0].c2>>Dp[0].c3
          >>Dp[0].c4)
    {
        if(N==0&&Dp[0].c1==0&&Dp[0].c2==0
           &&Dp[0].c3==0&&Dp[0].c4==0)
            break;
        
        memset(Used,false,sizeof(Used));
        Used[0]=true;

        for(int i=1;i<=N;i++)
        {
            flag=i;
            left_count=Dp[0].c1+Dp[0].c2+Dp[0].c3+Dp[0].c4;
            if(i-1>=0&&Used[i-1]&&Dp[i-1].c1-1>=0)
            {
                int tm=Dp[i-1].c1+Dp[i-1].c2+Dp[i-1].c3+
                    Dp[i-1].c4-1;
                if(tm<left_count){
                    left_count=tm;
                    flag=i-1;
                }
            }
            if(i-5>=0&&Used[i-5]&&Dp[i-5].c2-1>=0)
            {
                int tm=Dp[i-5].c1+Dp[i-5].c2+Dp[i-5].c3+
                    Dp[i-5].c4-1;
                if(tm<left_count){
                    left_count=tm;
                    flag=i-5;
                }
            }
            if(i-10>=0&&Used[i-10]&&Dp[i-10].c3-1>=0)
            {
                int tm=Dp[i-10].c1+Dp[i-10].c2+Dp[i-10].c3+
                    Dp[i-10].c4-1;
                if(tm<left_count){
                    left_count=tm;
                    flag=i-10;
                }
            }
            if(i-25>=0&&Used[i-25]&&Dp[i-25].c4-1>=0)
            {
                int tm=Dp[i-25].c1+Dp[i-25].c2+Dp[i-25].c3+
                    Dp[i-25].c4-1;
                if(tm<left_count){
                    left_count=tm;
                    flag=i-25;
                }
            }
            if(flag!=i){
                Used[i]=true;
                Dp[i].c1=Dp[flag].c1;
                Dp[i].c2=Dp[flag].c2;
                Dp[i].c3=Dp[flag].c3;
                Dp[i].c4=Dp[flag].c4;
                if(flag==(i-1))
                    Dp[i].c1--;
                else if(flag==(i-5))
                    Dp[i].c2--;
                else if(flag==(i-10))
                    Dp[i].c3--;
                else if(flag==(i-25))
                    Dp[i].c4--;
            }
        }
        if(!Used[N])
        {
            printf("Charlie cannot buy coffee.\n");
        }
        else
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",
                   Dp[0].c1-Dp[N].c1,Dp[0].c2-Dp[N].c2,Dp[0].c3-Dp[N].c3,Dp[0].c4-Dp[N].c4);
    }
    return 0;
}