【每日一题】Quasi Binary 题解

Description

A number is called quasibinary if its decimal representation contains only digits 0 or 1. For example, numbers 0, 1, 101, 110011 — are quasibinary and numbers 2, 12, 900 are not.

You are given a positive integer n. Represent it as a sum of minimum number of quasibinary numbers.

Solution

重点：
显然符合条件的0,1整数很少(64个),通过dfs能够得到它们，随后问题转化成了：给定一个数字 n, 和一堆数字，问最少能用几个数字组成n
思路：dp
容易想到状态转移方程 dp[i] = min(dp[i], dp[i - j] + 1), j 为符合条件的01整数
加一个数组记录前驱即可
时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int dp[N], pre[N];
int n;
vector<int> v;
int solve(string s) {
  int res = 0;
  for(auto &x : s) {
    res = res * 10 + x - '0';
  }
  return res;
}
void dfs(string s) {
  //cout << s.size() << '\n';
  int num = solve(s);
  if(num > n) return ;
  v.push_back(solve(s));
  dfs(s + '0');
  dfs(s + '1');
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> n;
  dfs("1");
  sort(v.begin(), v.end());
  //for(auto x : v) cout << x << ' ';
  //cout << v.size() << '\n';
  memset(dp, 0x3f, sizeof(dp));
  memset(pre, -1, sizeof(pre));
  dp[0] = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < v.size() && v[j] <= i; j++) {
      if(dp[i] > dp[i - v[j]] + 1) {
        dp[i] = dp[i - v[j]] + 1;
        pre[i] = v[j];
      }
    }
  }
  cout << dp[n] << '\n';
  while(pre[n] != -1) {
    cout << pre[n] << ' ';
    n = n - pre[n];
  }
  return 0;
}