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