链接：https://ac.nowcoder.com/acm/contest/338/F
来源：牛客网
The first line contains an integer T (1 <= T <= 100 ).
The following T lines contain an interger n ( 0 <= n <= 1e18 ).
For the last T lines, output the total numbers of AFei numbers that are not greater than n.
For the first case, only 520 is AFei number.
For the second case, 520,1520, 2520, 3520, 4520, 5200, 5201, 5202, 5203, 5204, 5205, 5206, 5207, 5208, 5209 and 5520 are AFei number. So there are 16 AFei numbers.
#include<bits/stdc++.h> #define ll long long using namespace std; int temp[20]; ll dp[20][4]; ll dfs(int len, int s, bool limit) { if(len == 0) return s==3; if(!limit && dp[len][s] != -1) return dp[len][s]; int up = limit ? temp[len] : 9; ll sum = 0; for(int i = 0; i <= up; i ++) { int ss; if(s==3) ss=3; else if(i==5) ss=1; else if(s==1&&i==2) ss=2; else if(s==2&&i==0) ss=3; else ss=0; sum += dfs(len - 1, ss, limit && (i == up)); } if(!limit) dp[len][s] = sum; return sum; } ll solve(ll x) { int len = 0; while(x) { temp[++ len] = x % 10; x /= 10; } return dfs(len, 0, 1); } int main() { memset(dp,-1,sizeof(dp)); int T; scanf("%d", &T); while(T --) { ll b; scanf("%lld", &b); printf("%lld\n", solve(b)); } return 0; }
原文：https://www.cnblogs.com/DWVictor/p/10229999.html
