处女座和小姐姐（三）（数位dp）

链接：https://ac.nowcoder.com/acm/contest/329/G

来源：牛客网

题目描述

经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！

处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。

现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。

输入描述:

一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。

输出描述:

一行一个整数，表示处女座内心激动的次数。

示例1

输入

10 20

输出

1

备注:

0≤l≤r≤10^18

以后补一下数位dp，先把板子放这

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

typedef long long ll;

int a[70];

long long int dp[70];

long long int dfs(int pos,bool limit)

{

    if(pos==0) return 1;

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

    int up=limit ? a[pos] : 9;

    long long int tmp=0;

    for(int i=0;i<=up;i++)

    {

        if(i==6) continue;//都是保证枚举合法性

        tmp+=dfs(pos-1,limit && i==a[pos]);

    }

    if(!limit) dp[pos]=tmp;

    return tmp;

}

long long int solve(long long int x)

{

    int pos=0;

    long long n=x;

    if(x<=0)return 0;

    while(x)

    {

        a[++pos]=x%10;

        x/=10;

    }

    return n+1-dfs(pos,true);

}

int main()

{

    long long int le,ri;

    //memset(dp,-1,sizeof dp);可优化

    while(~scanf("%lld%lld",&le,&ri))

    {

        memset(dp,-1,sizeof dp);

        printf("%lld\n",solve(ri)-solve(le-1));

    }

    return 0;

}