学步园

为了让智硬的自己以后还能看懂，尽量写详细点><

数位DP是按位考虑状态，然后再涉及到每一位数字的大小关系。

这里面用dp[i][0]表示i位数不包含49的个数，dp[i][1]表示i位数不包含49的但是以9开头的个数，dp[i][2]表示i位数包含49的个数，注意dp[i][0]包含了dp[i][1]，最后枚举的时候不要算重了。

这里面的递推关系是从后i-1位推到后i位，新加的第i位的数位于高位。这里面的dp[i][j]是整个i位数所有数中有没有49，在下面的状态转移过程中还会根据input number每一位数的大小进行更新。

举个例子就可以找出递推关系：

_X49XX->XX49XX

_9XXXX->49XXXX

_XXXXX->9XXXX or XXXXX

因为新加的第i位可以填0-9共十个数，因此：

dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//要减去49XXX的case
dp[i][1]=dp[i-1][0];//直接在最高位填上9
dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//要加上49XXX的case

后面的递推是从高位往低位推，智硬的我想了好久=。= 最后发现举个例子一目了然(⊙o⊙)…可见动手写一写还是比瞎想有作用，上次比赛要是多画几个sample那一题公式弄不好就弄出来了><

for example, n=5673

i=4：

0~4 [后面的数包含49]

4 [后面的数不包含49但是以9开头]

注意这里面最高位没有考虑5，因为dp[3][0 or 1 or 2]考虑的是0-999里面的数，所以这一位考虑5可能就会包含超出n的case

i=3:

5 0~5 [后面的数包含49]

5
4 [后面的数不包含49但是以9开头]

i=4的位置没有填5，所以i=3时在i=4处填的是5，因此不同的i对应的是disjoint sample space，所以最后的ans要加起来。

i=2:

5 6
0~6 [后面的数包含49]

5 6
4 [9XXXX]

i=1:

5 6 7
0~2 [XXX49XX]

由此可见，枚举的上界不会达到，最后枚举的只考虑了0~n-1的case，所以最初要n++。

然后要注意ans要设成long long，最后的数真心会很大（预处理的dp都出现了负的==）

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;

int T;
long long N;
const int maxn=20;
long long dp[maxn][3];
int digit[maxn];
long long ans;
int len;
void initial()
{
    memset(dp,0,sizeof(dp));

    dp[0][0]=1;//0位数（null）不为49有一种方案，空方案作为一种方案
    dp[0][1]=0;
    dp[0][2]=0;
    for(int i=1;i<maxn;i++)
    {
        dp[i][0]=dp[i-1][0]*10-dp[i-1][1];
        dp[i][1]=dp[i-1][0];
        dp[i][2]=dp[i-1][2]*10+dp[i-1][1];
        //cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<endl;
    }
}
void getdigit()
{
    len=0;
    memset(digit,0,sizeof(digit));
    N++;
    memset(digit,0,sizeof(digit));
    while(N>0)
    {
        digit[++len]=N%10;
        N/=10;
    }
}
void DP()
{
    ans=0;//为什么ANS要加起来？
    bool flg=false;
    int last=0;
    for(int i=len;i>=1;i--)
    {
        ans+=dp[i-1][2]*digit[i];//如果后面的数包含49，这一位填什么数都无所谓，只要比N小
       // cout<<" 1 "<<i<<" "<<ans<<endl;
        if(flg)//如果高位出现过49（不一定是紧邻的前两位），后面可以填没有49的数
        {
            ans+=dp[i-1][0]*digit[i];
            //flg=false;
         //   cout<<" 2 "<<i<<" "<<ans<<endl;
        }
        if(!flg&&digit[i]>4)// 如果前面没有49，第i位可以填4，后面接以9开头的数。
        {//并且必须!flg才可以执行，因为dp[i][0]包含了dp[i][1]的case，所以前面出现过49，上一步已经包含了第i位填4，后面接以9开头的数的case。
            ans+=dp[i-1][1];
        //    cout<<" 3 "<<i<<" "<<ans<<endl;
        }
        if(last==4&&digit[i]==9)
        {
            flg=true;
        }
        last=digit[i];
    }
    printf("%I64d\n",ans);
}
int main()
{
    freopen("input.txt","r",stdin);
    // freopen("data.txt","r",stdin);
     //freopen("out1.txt","w",stdout);
     scanf("%d",&T);
     initial();
     for(int i=0;i<T;i++)
     {
         scanf("%I64d",&N);

         getdigit();
         DP();

     }

     return 0;
}