It is a straight forward dp problem.Use a memoized version. it is pretty
simple.
#include<iostream>
#include<map>
using namespace std;
map <long long int,long long int> p;
main()
{
long long int a,f;
long long int fun(long long int );
p.clear();
while(cin>>a)
{
f=fun(a);
cout<<f<<endl;
}
}
long long int fun(long long int a)
{
long long int ch,q;
if(a==0)
return 0;
if(p.find(a)!=p.end())
return p[a];
else
{
ch=fun(a/2)+fun(a/3)+fun(a/4);
if(ch>=a)
p[a]=ch;
else
p[a]=a;
}
return p[a];
}
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.
