zoj 2156 - Charlie's Change

称号：拼布钱，表面值至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; }