c/c++语言开发共享洛谷P4133 [BJOI2012]最多的方案(记忆化搜索)

// luogu-judger-enable-o2  #include<cstdio>  #include<iostream>  #include<map>  #define pair pair<int, int>  #define mp(x, y) make_pair(x, y)  #define fi first  #define se second   #define int long long  #define ull unsigned long long    using namespace std;  const int maxn = 1e5 + 10;  inline int read() {      char c = getchar(); int x = 0, f = 1;      while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}      while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();      return x * f;  }  int f[maxn], tot, lim, dp[maxn], n;  map<pair, int> mp;  int dfs(int x, int ti) {      if(mp.find(mp(x, ti)) != mp.end()) return mp[mp(x, ti)];      if(x == 0) return 1;      int ans = 0;      /*for(int i = ti; i >= 1; i--) {          if(x - f[i] >= 0) ans += dfs(x - f[i], i - 1);          //else break;      }*/      if(x - f[ti] >= 0) ans += dfs(x - f[ti], ti - 1);      if(x < f[ti + 1])           ans += dfs(x, ti - 1);            return mp[mp(x, ti)] = ans;  }  main() {      lim = 1e18;      f[1] = 1; f[2] = 2;      for(int i = 3; i; i++) {          f[i] = f[i - 1] + f[i - 2];          if(f[i] > lim) {tot = i; break;}      }      n = read();      //dp[0] = 1;      cout << dfs(n, tot - 1);      return 0;  }