称号：拼布钱，表面值至1，5。10。25。寻求组成n表面值硬币的最大数目。

分析：dp，01背包。需要二元分割，除此以外TLE。使用每个硬币的数组记录数。轻松升级。

写了一个 多重背包的 O（NV）反而没有拆分快。囧，最后利用了状态压缩优化 90ms；

把 1 cents 的最后处理，其它都除以5，状态就少了5倍了。

说明：貌似我的比大黄的快。（2011-09-26 12:49）。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define INF -100001

#define min( a, b ) ((a)<(b)?

(a):(b))

int t[ 5 ];

int F[ 2001 ][ 5 ];

int C[ 5 ] = {0,1,1,2,5};

int T[ 5 ][ 15 ];

int main()

{

    int P,Q;

    while ( scanf("%d",&P) != EOF ) {

        for ( int i = 1 ; i <= 4 ; ++ i )

            scanf("%d",&t[ i ]);

        if ( !P ) break;

        Q = P%5;

        P = P/5;

        if ( t[ 1 ] < Q ) {

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

            continue;

        }t[ 1 ] -= Q;t[ 1 ] /= 5;

        memset( F, 0, sizeof( F ) );

        for ( int i = 1 ; i <= P ; ++ i )

            F[ i ][ 0 ] = INF;

        F[ 0 ][ 0 ] = F[ 0 ][ 1 ] = Q;

        //二进制拆分

        for ( int i = 2 ; i <= 4 ; ++ i ) {

            int base = 1,numb = 0;

            while ( t[ i ] >= base ) {

                T[ i ][ ++ numb ] = base;

                t[ i ] -= base;

                base <<= 1;

            }

            if ( t[ i ] ) T[ i ][ ++ numb ] = t[ i ];

            T[ i ][ 0 ] = numb;

        }

        for ( int i = 2 ; i <= 4 ; ++ i ) {

            int e = T[ i ][ 0 ];

            for ( int j = 1 ; j <= e ; ++ j ) {

                int v = T[ i ][ j ];

                int u = v*C[ i ];

                for ( int k = P ; k >= u ; -- k )

                    if ( F[ k-u ][ 0 ] >= 0 && F[ k ][ 0 ] < F[ k-u ][ 0 ]+v ) {

                        for ( int l = 0 ; l <= 4 ; ++ l )

                            F[ k ][ l ] = F[ k-u ][ l ];

                        F[ k ][ 0 ] += v;

                        F[ k ][ i ] += v;

                    }

            }

        }

        //处理 cents 的

        for ( int i = t[ 1 ] ; i >= 0 ; -- i )

            if ( F[ P-i ][ 0 ] >= 0 ) {

                int s = t[ 1 ];

                F[ P-i ][ 0 ] += i*5;

                F[ P-i ][ 1 ] += i*5;

                s -= i;

                for ( int j = 4 ; j > 1 ; -- j ) {

                    int v = min( s/C[ j ], F[ P-i ][ j ] );

                    F[ P-i ][ j ] -= v;

                    F[ P-i ][ 1 ] += v*C[ j ];

                     F[ P-i ][ 0 ] += v*(C[ j ]-1);

                     s -= v*C[ j ];

                }

            }

        int max = INF,spa = P;

        for ( int i = 0 ; i <= t[ 1 ] ; ++ i )

            if ( max < F[ P-i ][ 0 ] ) {

                max = F[ P-i ][ 0 ];

                spa = P-i;

            }

        if ( F[ spa ][ 0 ] <= 0 )

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

        else

            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",

                F[ spa ][ 1 ],F[ spa ][ 2 ],F[ spa ][ 3 ],F[ spa ][ 4 ]);

    }

    return 0;

}