Quasi Binary（BFS打表+背包DP）

题目大意：
给你一个数,要你找个数，使得这个数的和是，并且这些数只能包含。
思路：
先把的只包含01的数打表出来，这部分BFS即可，可以发现数量并不多刚好255个。
然后可以考虑背包dp求出最小的组成的方案，时间复杂度为不会超时。
dp[i]:用只包含01的数组成数字i的最小组成数量。
转移方程：dp[i] = min(dp[i],dp[i - res[j]] + 1)。
因为还要输出方案，再开一个数组记录当前位置的上一步骤，并且记录一下当前最优选择，然后输出一下即可。
代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn = 1e6 + 10;
int dp[maxn];//dp[i]:组成i的最小操作次数
int path[maxn];
int v[maxn]; 
void solved(){
    queue<int>st;st.push(1);
    vector<int>res;res.push_back(1);
    while(!st.empty()){
        int cur = st.front();st.pop();
        if(cur >= 10000000)break;
        for(int i = 0;i < 2; i++){
            st.push(cur * 10 + i);
            res.push_back(cur * 10 + i);
        }
    }
    sort(res.begin(),res.end());
    int n;cin>>n;
    for(int i = 1; i <= n; i++)dp[i] = 1e7;
    for(int i = 1; i <= n; i++){
        int x = 1e7;
        for(int j = 0; j < res.size(); j++){
            if(i - res[j] >= 0 && dp[i - res[j]] + 1 <= dp[i]){
                dp[i] = min(dp[i - res[j]] + 1,dp[i]);
                x = i - res[j];
                v[i] = res[j];
            }
        }
        path[i] = x;
    }
    cout<<dp[n]<<endl;
    while(path[n] != 0){
        cout<<v[n]<<" ";
        n = path[n];
    }
    cout<<v[n]<<endl;
}
int main(){
    solved();
    return 0;
}