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;
  }
};