CF538B Quasi Binary

• 前言

  大菜鸡早上做题，误视作贪心，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;
}