1787.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"

char set[10000];
int use[10000][4];
long total[10000];
int money[4]={1,5,10,25};

int limit[4],p;


void doit()
{int i,j,h,k;
memset(set,0,10000*sizeof(char));
memset(use,0,10000*4*sizeof(int));
set[0]=1;
total[0]=0;
for(i=0;i<4;i++)
for(j=0;j<=p-money[i];j++)
{h=j+money[i];
if(set[j]&&(!set[h]||total[h]<total[j]+1)&&use[j][i]<limit[i])
	{set[h]=1;
	for(k=0;k<4;k++)use[h][k]=use[j][k];
	use[h][i]=use[j][i]+1;
	total[h]=total[j]+1;
	}
}

return;
}

int main()
{int i;
	while(1)
{cin>>p;
for(i=0;i<4;i++)cin>>limit[i];
if(p==0)break;
doit();
if(set[p])cout<<"Throw in "<<use[p][0]<<" cents, "<<use[p][1]<<" nickels, "<<use[p][2]<<" dimes, and "<<use[p][3]<<" quarters."<<endl;
else cout<<"Charlie cannot buy coffee."<<endl;
}
return 0;
}