I get accepted on 10626 with a O(1) solution. But from the ranklist, it seems that someone use longer runtime and large memory to solve it. Is there any DP solution to this problem?? I am really curious to know
![:roll:](./images/smilies/icon_rolleyes.gif)
Thanks in advance.
Moderator: Board moderators
So I wonder how to use 32MB memory to hold all states.........ones_left=original_money-8*cokes_left-5*fives_left-10*tens_left;
Yes, I noticed this when I created the problem... was trying to figure out a case where it DID matter, only to realize there were no such case :-/on a side note, i found an interesting fact about this problem. the number of coins of value 1 doesnt matter. you dont need it to solve the problem... the answer will be the same regardless the number of coins of value 1 (provided of course the input is valid, ie you have enough money
Code: Select all
#include<stdio.h>
#define A 155
#define B 200
#define C 40
long a[A][B][C],m,noo,nff,ntt,nn;
long no,min,b;
main()
{
freopen("in.txt","r",stdin);
long cas,z,i,j,k,n,nf,nt;
scanf("%ld",&cas);
for(z=0;z<cas;z++)
{
scanf("%ld%ld%ld%ld",&nn,&noo,&nff,&ntt);
m=noo+5*nff+10*ntt;
for(i=0;i<A;i++) for(j=0;j<B;j++) for(k=0;k<C;k++) a[i][j][k]=0;
for(i=0;i<A;i++) a[i][0][0]=i*8;//any no. of 1
a[1][1][0]=4;//only one 5 + 3 1s
for(i=2;i<B;i++) a[1][i][0]=2;//if any no. of 5
for(i=0;i<B;i++) for(j=1;j<C;j++) a[1][i][j]=1;//any no of five+ any ten
for(n=2;n<A;n++) for(nf=0;nf<B-11;nf++) for(nt=0;nt<C;nt++)
{
min=1000000;
no=m-8*(nn-n)-5*nf-10*nt;
if(no<0) continue;
if (nt>=1 && no>=3) {b=a[n-1][nf+1][nt-1]+4;if(b<min) min=b;}
if (no>=0) {b=a[n-1][nf][nt]+8;if(b<min) min=b;}
if (nt>=1) {b=a[n-1][nf][nt-1]+1;if(b<min) min=b;}
if (nf>=2) {b=a[n-1][nf-2][nt]+2;if(b<min) min=b;}
if (nf>=1 && no>=3) {b=a[n-1][nf-1][nt]+4;if(b<min) min=b;}
a[n][nf][nt]=min;
}
printf("%ld\n",a[nn][nff][ntt]);
}
return 0;
}