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;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:cas单点登录 SSO 的实现原理


下一篇:JAVA CAS单点登录(SSO) 教程