{}动态规划}记忆化dp

 1 #include<stdio.h>
 2 #include<string.h>
 3 using namespace std;
 4 typedef long long ll;
 5 int a[20];
 6 ll dp[20][2];
 7 ll dfs(int pos,bool six,bool limit)
 8 {
 9     if(pos==0) return six?1:0;
10     int state=six?1:0;
11     if(!limit&&dp[pos][state]!=-1) return dp[pos][state];
12     int up=limit?a[pos]:9;
13     ll ans=0;
14     for(int i=0;i<=up;++i)
15     {
16         ans+=dfs(pos-1,six||i==6,limit&&i==a[pos]);
17     }
18     if(!limit) dp[pos][state]=ans;
19     return ans;
20 }
21 ll solve(ll x)
22 {
23     memset(dp, -1, sizeof(dp));
24     int pos=0;
25     while(x)
26     {
27         a[++pos]=x%10;
28         x/=10;
29     }
30     return dfs(pos,0,1);
31 }
32 int main()
33 {
34     ll le,ri;
35     scanf("%lld %lld",&le,&ri);
36     printf("%lld\n",solve(ri)-solve(le-1));
37     return 0;
38 }