【51NOD】数字1的数量

【算法】数位DP

【题解】数位dp总结 之 从入门到模板

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

int n,a[maxn],NUM[maxn];

long long f[maxn];

struct cyc{int num/*数字数*/;long long ans/*1的数量*/;}qp;

cyc dfs(int deep,bool limit)//返回1的个数

{

    if((f[deep]!=-&&!limit)||deep==)

    {

        qp.num=NUM[deep];

        qp.ans=f[deep];

        return qp;

    }

    int k=limit?a[deep]:;

    int sum=;long long ans=;

    for(int i=;i<=k;i++)

    {

        qp=dfs(deep-,limit&&i==k);

        if(i==)ans+=qp.num;

        ans+=qp.ans;

        sum+=qp.num;

    }

    if(!NUM[deep]&&!limit)NUM[deep]=sum;

    if(f[deep]==-&&!limit)f[deep]=ans;

    qp.ans=ans;qp.num=sum;

    return qp;

}

int main()

{

    scanf("%d",&n);

    int k=n;int N=;

    while(k>)

    {

        N++;

        a[N]=k%;

        k/=;

    }

    memset(f,-,sizeof(f));

    NUM[]=;f[]=;

    printf("%lld",dfs(N,).ans);

    return ;

}