BadNeighbors メモ化再帰版 TCCC '04 Round 4

• メモ化再帰版
  • 再帰する時に、同じ計算を何回もやるような場合は、メモを入れちゃえば、圧倒的に早くなる。
  • DPと両方使えるようになりたい。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;


class BadNeighbors{
public:
  vector<int> ans;
  vector<int> val;

  int dfs(int n){
    if(n < 0) return 0;
    if(ans[n] > 0) return ans[n];
    return ans[n] = max(dfs(n - 1), dfs(n - 2) + val[n]);
  }

  int doit(int s, int e, vector<int> donations){
    int n = e - s;
    ans.resize(n); fill(ans.begin(), ans.end(), 0);
    val.resize(n);
    copy(&donations[s], &donations[e], val.begin());
    return dfs(n - 1);
  }

  int maxDonations(vector <int> donations){
    int n = donations.size();
    return max(doit(0, n - 1, donations),
	       doit(1, n, donations));
  }


};