Quasi Binary（完全背包）

题目：

给你一个 $n$ ，让你将其拆成最少的若干个十进制数的和，这些十进制数只由 $0$ 和 $1$ 构成。要求输出方案。
$n≤1e6$

做法：

这些特殊的十进制数其实与二进制数一一对应， $1e6$ 以内只有 $2^6+1 = 65$ 个（对应于 $6$ 位以内二进制数和 $(1000000)_2$ ）。我们考虑先将 $n$ 以内的数先求出来。然后这就变成了一个完全背包问题，要求输出方案。方案用一个 $path[]$ 辅助记录当前最后一个选的数即可。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
int a[N], dp[N], path[N];   
int trans(int x){
    int ans = 0;
    for (int bas = 1; x; x >>= 1, bas *= 10) if (x&1) ans += bas;
    return ans;
}
void dfs(int n){
    if (!path[n]) return;
    dfs(n-path[n]);
    cout << path[n] << ' ';
}
int main(void){
    IOS;
    int n, m = 0; cin >> n;
    for (int i = 0, x = trans(i); x <= n; ++i, x = trans(i)) a[++m] = x;
    memset(dp, inf, sizeof dp); dp[0] = 0;
    for (int i = 1; i <= m; ++i){
        for (int j = a[i]; j <= n; ++j){
            if (dp[j] > dp[j-a[i]]+1) dp[j] = dp[j-a[i]]+1, path[j] = a[i];
        }
    }
    cout << dp[n] << endl;
    dfs(n);
    return 0;
}