Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <map>
- using namespace std;
- class TrafficCongestionDivTwo{
- public:
- long theMinCars(int treeHeight){
- if(treeHeight == 0 || treeHeight == 1)
- return 1;
- if(isCalc(treeHeight)){
- return mem[treeHeight];
- }
- long result = 1;
- for(int h = (treeHeight - 2); h >= 0; h--) {
- result += 2 * theMinCars(h);
- }
- mem[treeHeight] = result;
- return result;
- }
- private:
- map<int, long> mem;
- bool isCalc(int height){
- return mem.find(height) != mem.end();
- }
- };
- int main() {
- int h;
- cin >> h;
- TrafficCongestionDivTwo t;
- cout << t.theMinCars(h) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement