TopCoder SRM 687 Div1 Easy: AlmostFibonacciKnapsack
解法
当たりそうなところだけを持っていればおk
コード
#include <algorithm> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; typedef long long ll; class AlmostFibonacciKnapsack { public: vector<int> getIndices(long long x) { vector<ll> A; A.push_back(2); A.push_back(3); for (;;) { size_t s = A.size(); ll N = A[s - 1] + A[s - 2] - 1; if (N > x) break; A.push_back(N); } vector<ll> sum(A); for (int i = 1; i < sum.size(); ++i) { sum[i] += sum[i - 1]; } map<ll, vector<int>> dp; dp[0].push_back(-1); for (int i = A.size() - 1; i >= 0; --i) { map<ll, vector<int>> tmp; for (const auto &p : dp) { ll next = p.first + A[i]; if (i > 0 && next + sum[i - 1] < x) continue; if (next > x) continue; tmp[next] = p.second; tmp[next].push_back(i); } for (const auto &p : tmp) if (!dp.count(p.first)) dp[p.first] = p.second; } if (dp.count(x)) { vector<int> ans; ll check = 0; for (const auto &i : dp[x]) { if (i >= 0) { check += A[i]; ans.push_back(i + 1); } } assert(check == x); return ans; } vector<int> hoge; hoge.push_back(-1); return hoge; } };