小米oj 找小"3"（数位dp)

找小“3”

序号：#40难度：困难时间限制：1000ms内存限制：10M

描述

给定一个奇数n，可得到一个由从1到n的所有奇数所组成的数列，求这一数列中数字3所出现的总次数。例如当n=3时，可得到奇数列：1,3，其中有一个数字3，故可得1

输入

一个奇数。表示n，0<n<9999999999。

输出

一个整数，表示从 1 到 n 的奇数列中，数字 3 出现的次数。

输入样例

复制样例

输出样例

#include<iostream>

#include<string.h>

#include<stdio.h>

#include<algorithm>

using namespace std;

typedef long long ll;

int bit[15];

ll n;

ll ans;

ll dp[15];

ll mypow(ll a,ll b)

{

    if(b==0)return 2;

    ll ret=1;

    while(b--)ret*=a;

    return ret;

}

ll get(ll p)

{

    if(p==0)return 1;

    ll tmp=1;ll res=0;

    for(ll i=1;i<=p;i++)

    {

        res+=bit[i]*tmp;

        tmp*=10;

    }

    return res;

}

ll dfs(ll pos,bool flag)

{

    if(flag&&dp[pos]!=-1)return dp[pos];

    if(pos==0)return 0;

    ll x=flag?9:bit[pos];

    ll res=0;

    for(ll i=0;i<=x;i++)

    {

        if(i==3){

            if(flag||i<x){res+=mypow(10,pos-1)/2;}

            else {

                res+=(get(pos-1)+1)/2;

            }

           res+=dfs(pos-1,flag||i<x);

        }

        else {

           res+=dfs(pos-1,flag||i<x);

        }

    }

    if(flag)dp[pos]=res;

    return res;

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(~scanf("%lld",&n))

    {

        memset(dp,-1,sizeof(dp));

        int cnt=0;

        while(n)

        {

            bit[++cnt]=n%10;

            n/=10;

        }

        ans=dfs(cnt,0);

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

小米oj 找小"3"（数位dp)

最新文章

热门文章