#DP #MemorizingInMap #Solved #SPOJ

COINS - Bytelandian gold coins.cpp

//http://www.spoj.com/problems/COINS/
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;

map<int, ll> cache;

ll calcMax(int x) {
    if(x <= 2)
        return x == 0 ? 0 : x;

    if(cache.find(x) != cache.end())
        return cache[x];
    ll &ret = cache[x];
    ll y = calcMax(x/2) + calcMax(x/3) + calcMax(x/4);
    ret = (x > y) ? x : y;

    return ret;
}

int main() {
    cache.clear();
    int n;
    while(cin>>n)
        cout << calcMax(n) << endl;
    return 0;
}