学步园

这是最简单的数位dp,也是我第一道数位dp....话说以前这样的题，根本不敢下手。只有下手了，挑战了，才能逐步战胜困难。畏惧是永远不行的

对于数位的问题，要逐位化简。之前看了看cxlove大湿的博客，看了几行，也就是dp的状态和阶段，当然转移方程完全没看。

dp[i][0]:从0~(10^i-1)有多少个数不含“49”

dp[i][2]:从0~(10^i-1)有多少个数含“49”

重点是dp[i][1]:从0~(10^i-1)有多少个是不含“49”的且以9为打头的，这是个衔接状态，很重要

状态转移就看程序吧，因为这个搞了不少WA。。。。最后搜索时注重细节，附代码：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <vector>

#define N 20
#define ll __int64 
#define ss(a) scanf("%I64d",&a)
#define pb push_back

using namespace std;

ll dp[N][4],a[N],c[N];
vector<int>b;
int x;

ll deal(int k)
{
    if (k<0) return x+1;
    if (k<x) return a[k]+1;
    else 
    {
        if (b[k]<=4) return b[k]*dp[k][2]+deal(k-1);
        else return b[k]*dp[k][2]+dp[k][1]+deal(k-1);
    }
}

int main()
{
    int i,T;
    ll n;
    dp[0][0]=1;c[0]=1;
    for (i=1;i<N;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];
        c[i]=c[i-1]*10;
    }
    cin>>T;
    while (T--)
    {
        ss(n);
        b.clear();
        while (n>0)
        {
            int k=b.size();
            if (k==0) a[0]=n%10;
            else a[k]=(n%10)*c[k]+a[k-1];
            b.pb(n%10);
            n/=10;
        }
        x=-1;
        for (i=b.size()-2;i>=0;i--) 
            if (b[i+1]*10+b[i]==49) 
            {
                x=i;break;
            }
        printf("%I64d\n",deal(b.size()-1));
    }
    return 0;
}