洛谷 P4124 [CQOI2016]*

题目传送门

解题思路:

搜的时候记录8,4和三连就行.
AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 long long l,r;
 8 int s[15],f[15][15][15][2][2][2][2],len;
 9 
10 inline long long dfs(int d,int p,bool li,bool _4,bool _8,int xs,bool vis,int o) {
11     if(d > len) return vis | 0;
12     if(f[d][p][o][li][_4][_8][vis] != -1) return f[d][p][o][li][_4][_8][vis];
13     long long ans = 0;
14     int res = li ? s[len-d+1] : 9;
15     for(int i = (d == 1) ? 1 : 0;i <= res; i++) {
16         if((i == 4 && _8) || (i == 8 && _4)) continue;
17         if(i == p) ans += dfs(d + 1,i,li && (i == res),_4 || (i == 4),_8 || (i == 8),xs + 1,vis || ((xs + 1) >= 3),p);
18         else ans += dfs(d + 1,i,li && (i == res),_4 || (i == 4),_8 || (i == 8),1,vis || (xs >= 3),p);
19     }
20     f[d][p][o][li][_4][_8][vis] = ans;
21     return ans;
22 }
23 
24 inline long long solve(long long x) {
25     len = 0;
26     while(x) {
27         s[++len] = x % 10;
28         x /= 10;
29     }
30     memset(f,-1,sizeof(f));
31     if(len < 11) return 0;
32     return dfs(1,-1,1,0,0,1,0,-1);
33 }
34 
35 int main() {
36     scanf("%lld%lld",&l,&r);
37     printf("%lld",solve(r) - solve(l - 1));
38     return 0;
39 }