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