Advertisement
jcvitanovic

Auteki

Mar 30th, 2015
226
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <map>
  4.  
  5. using namespace std;
  6.  
  7. class TrafficCongestionDivTwo{
  8. public:
  9.     long theMinCars(int treeHeight){
  10.         if(treeHeight == 0 || treeHeight == 1)
  11.             return 1;
  12.         if(isCalc(treeHeight)){
  13.             return mem[treeHeight];
  14.         }
  15.         long result = 1;
  16.         for(int h = (treeHeight - 2); h >= 0; h--) {
  17.             result += 2 * theMinCars(h);
  18.         }
  19.         mem[treeHeight] = result;
  20.         return result;
  21.     }
  22. private:
  23.     map<int, long> mem;
  24.     bool isCalc(int height){
  25.         return mem.find(height) != mem.end();
  26.     }
  27. };
  28. int main() {
  29.     int h;
  30.     cin >> h;
  31.     TrafficCongestionDivTwo t;
  32.     cout << t.theMinCars(h) << endl;
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement