算法1
(记忆化搜索)
枚举每一位,直到最后,对最终数量贡献1,
当前一位是6或者前一位到达上限的时候不能用记忆化的结果,其余时候直接用记忆化搜索的结果即可
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int C = 11;
int a[C], len;
long long f[C];
int dfs(int pos, int pre, bool limit) {
if (!pos) return 1;
if (!limit && pre != 6 && f[pos] != -1) return f[pos];
int cnt = 0, up_bound = limit ? a[pos] : 9;
for (int i = 0; i <= up_bound; i ++) {
if (i == 4 || (i==2 && pre == 6)) continue;
cnt += dfs(pos - 1, i, limit & (i == a[pos]));
}
return limit | (pre == 6) ? cnt : f[pos] = cnt;
}
int solve(int x) {
len = 0;
memset(f, -1, sizeof f);
while (x) {
a[++len] = x % 10;
x /= 10;
}
return dfs(len, 0, true);
}
int main(){
int n, m;
while (cin >> n >> m, n | m) {
cout << solve(m) - solve(n-1) << endl;
}
return 0;
}