SRM403 Div2 Hard

1000

DPするだけ。

const int N = 1000000 + 10;

vector<int> v;

void rec(int n)
{
  if (N <= n) return ;
  if (n) v.push_back(n);
  rec(n * 10 + 4);
  rec(n * 10 + 7);
  return ;
}

class TheSumOfLuckyNumbers {
public:
  vector <int> sum(int n)
  {
    rec(0);

    const int inf = 1 << 29;

    pair<int, int> dp[N];
    fill(dp, dp + N, make_pair(inf, -1));
   
    for (int i = 0; i < (int)v.size(); ++i) {
      dp[v[i]] = make_pair(1, v[i]);
    }

    for (int i = 0; i < (int)N; ++i) {
      if (dp[i].first == inf) continue;
      for (int j = 0; j < (int)v.size(); ++j) {
        int k = i + v[j];
        if (k < N) {
          dp[k] = min(dp[k], make_pair(dp[i].first + 1, v[j]));
        }
      }
    }

    vector<int> ret;
    if (dp[n].first == inf) return ret;
   
    while (n) {
      ret.push_back(dp[n].second);
      n -= dp[n].second;
    }
    sort(ret.begin(), ret.end());
    return ret;
  }
};