题目描述
远古的 Pascal 人也使用阿拉伯数字来进行计数，但是他们又不喜欢使用 7 7 7，因为他们认为 7 7 7 是一个不吉祥的数字，所以 Pascal 数字 8 8 8 其实表示的是自然数中的 7 7 7， 18 18 18 表示的是自然数中的 16 16 16。下面计算一下，在正整数 n n n 范围以内包含有多少个 Pascal 数字。

输入格式
第一行为正整数 t t t，接下来 t t t 行，每行一个正整数 n ( ≤ 2 32 − 1 ) n(≤2^{32}-1) n(≤232−1)。
输入的是 Pascal 数字
t ≤ 10000 t \leq 10000 t≤10000

输出格式
对于每个正整数 n n n，输出 n n n 以内的 Pascal 数的个数。

输入输出样例
输入 #1
2
10
20

输出 #1
9
18

---

这样一道难题怎么能让广大谷民做的如此之水呢！

推翻模拟暴政，世界属于dp！！！11

言归正传，这道题是一道很裸的数位dp

#include <iostream>
#include <cstring>

using namespace std ;

int a[1005] ;
long long f[1005] ; // f[i]:从第 i 位往后的满足条件的数字

long long dfs(int len , int less) // 记忆化搜索
{
	if (len == 0) return 1 ;
	if (!less && f[len] != -1) return f[len] ;
	int ed = less ? a[len] : 9 ;
	long long ret = 0 ;
	for (int i = 0 ; i <= ed ; i++)
		if (i != 7) ret += dfs(len - 1 , less && i == ed) ; // 如果不等于7，记下结果。
	if (!less) f[len] = ret ;
	return ret ;
}

long long solve(long long x)
{
	int len = 0 ;
	while (x)
	{
		a[++len] = x % 10 ;
		x /= 10 ;
	}
	return dfs(len , 1) ;
}

int main() {
	memset(f , -1 , sizeof f) ;
	int t ;
	cin >> t ; 
	long long r ;
	while(t--)
	{
		cin >> r ;
		cout << solve(r) - solve(0) << endl ; // 此处也可以将 solve(0) 更改为 1
	}
	return 0 ;
}

完美的结束！！！