Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
- -多重背包+路径记录500+MS#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int MAXN=10010; int f[MAXN], path[5][MAXN]; int p; void put(int v,int num,int kd) { int i, j; if(v*num>=p) { for(i=v; i<=p; i++) { if(f[i-v]>=0) { f[i]=max(f[i-v]+1,f[i]); if(f[i]==f[i-v]+1) { path[kd][i]=path[kd][i-v]+1; for(j=kd-1; j>0; j--) path[j][i]=path[j][i-v]; } } } return; } int k=1; while(k<num) { for(i=p; i>=k*v; i--) { if(f[i-k*v]>=0) { f[i]=max(f[i-k*v]+k,f[i]); if(f[i]==f[i-k*v]+k) { path[kd][i]=path[kd][i-k*v]+k; for(j=kd-1; j>0; j--) path[j][i]=path[j][i-k*v]; } } } num-=k; k*=2; } for(i=p; i>=num*v; i--) { if(f[i-num*v]>=0) { f[i]=max(f[i-num*v]+num,f[i]); if(f[i]==f[i-num*v]+num) { path[kd][i]=path[kd][i-num*v]+num; for(j=kd-1; j>0; j--) path[j][i]=path[j][i-num*v]; } } } } int main() { int i, j, t[5], ct[5]= {0,1,5,10,25}; while(scanf("%d%d%d%d%d",&p,&t[1],&t[2],&t[3],&t[4])!=EOF) { if(!p&&!t[1]&&!t[2]&&!t[3]&&!t[4]) break; f[0]=0; for(i=1; i<=p; i++) f[i]=-1; for(i=1; i<=4; i++) { for(j=0; j<=p; j++) path[i][j]=0; put(ct[i],t[i],i); } if(f[p]<0) printf("Charlie cannot buy coffee.\n"); else printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",path[1][p],path[2][p],path[3][p],path[4][p]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator