前言
大菜鸡早上做题,误视作贪心,QwQ
分析
这就是一个背包问题。因为 n<=1e6 ,可以dfs枚举出所有只含0和1的数。然后,就是一个完全背包。只是在转移的时候记录一下从哪个地方转移过来的,然后回溯就能找到答案。
代码
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,tot; int ans[N],dp[N],pre[N]; inline void Get(int now) { if(now>n) return ; ans[++tot]=now; Get(now*10+1); Get(now*10); } inline void dfs(int now) { if(!now) return ; dfs(pre[now]); printf("%d ",now-pre[now]); } int main() { scanf("%d",&n); Get(1); sort(ans+1,ans+tot+1); tot=unique(ans+1,ans+tot+1)-ans-1; memset(dp,0x3f,sizeof(dp));dp[0]=0; for (int i=1;i<=tot;i++) for (int j=ans[i];j<=n;j++) if(dp[j-ans[i]]+1<dp[j]) { dp[j]=dp[j-ans[i]]+1; pre[j]=j-ans[i]; } printf("%d\n",dp[n]);dfs(n); return 0; }