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

 找小“3”

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

描述

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

输入

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

输出

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

输入样例

1
3
35

 复制样例

输出样例

0
1
7

#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
",ans);
    }
    return 0;
}