图片说明
题目大意:
给你一个数,要你找个数,使得这个数的和是,并且这些数只能包含
思路:
先把的只包含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;
}