数位dp-Bomb

 

 

难受啊！！越做题是越感觉菜，这个又被几个坑给卡住了（只有我这个学渣才会卡）

 

坑点：1.考虑n是否已包含49，有的话还要再+1.

2， 注意从最高开始考虑时，再判断时要考虑它本身为0的情况，.比如n=5701，在考虑最高位时，其实是在考虑0~5000所能组成的含49的数的个数，这个是包含f[i][2]中的前导0并且千位最高位也可为0

#include<bits/stdc++.h>
using namespace std;
//#define LL long long
typedef __int64 LL;
LL f[25][10];
int n[200];
void init()
{
//    f[1][9]=1;
//    f[1][0]=10;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1; i<=22; i++)
    {
        f[i][1]=f[i-1][1]*10+f[i-1][9];
        f[i][9]=f[i-1][0];
        f[i][0]=f[i-1][0]*10-f[i-1][9];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    init();
//    for(int i=1;i<=20;i++)
//        printf("%lld\n",f[i][1]+f[i][0]);
    while(t--)
    {
//        string s;
//        cin>>s;
//        for(int i=0; i<s.size(); i++)
//            n[s.size()-i]=s[i]-'0';
        LL a;
        scanf("%I64d",&a);
        int len=0;
        LL ans=0;
        int flag=0;
        a++;
        while(a)
        {
            n[++len]=a%10;
            a/=10;
        }
        n[len+1]=0;
        for(int i=len; i>=1; i--)
        {
            ans+=n[i]*f[i-1][1];
            if(flag)
                ans+=n[i]*f[i-1][0];
            else if(n[i]>4)
                ans+=f[i-1][9];
            if(n[i+1]==4&&n[i]==9)
                flag=1;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}