Brute-force algorithm with memoization for this problem!
/*
Autor: Wladimir Araújo Tavares
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
int memo[3001][1001];
int banana(int V, int D){
int total;
int j;
int temp;
if(V < D) return 0;
if(memo[V][D]!=-1) return memo[V][D];
//one travel
if(V>1000)
total = 1000 - D;
else
total = V-D;
//more than one
if(V>1000){
temp = banana(V-1000, D) + 1000-2*D;
}else{
temp = V-D;
}
total = max(total, temp);
//cache
for(j=1;j<D;j++){
temp = banana(banana(V,j),D-j);
if(temp > total)
total = temp;
}
memo[V][D] = total;
return total;
}
int main(){
int x,i,j;
for(i=1;i<=3000;i++)
for(j=1;j<=1000;j++)
memo[i][j] = -1;
while(1){
scanf("%d",&x);
printf("%d\n",banana(3000,x));
}
return 0;
}
Wladimir Araujo Tavares
*Federal University of Ceará
*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
