杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。
例如： 62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
题目链接🔗
题解
数位DP，位内分类讨论
代码
#include <cstdio>
#include <algorithm>
using namespace std;
long long n, arr[12], dp[12][12];
void init() {
dp[0][0] = 1; // 前i个数首位为j的不包含62和4的个数
for (int i = 1; i <= 10; i++)
for (int j = 0; j <= 9; j++)
for (int k = 0; k <= 9; k++)
if (j != 4 && !(j == 6 && k == 2))
dp[i][j] += dp[i - 1][k];
}
long long solve(long long n) {
long long len = 0ll, ans = 0ll;
while (n) arr[++len] = n % 10, n /= 10;
arr[len + 1] = 0;
//printf("%lld ",dp[len][0]);
for (int i = len; i > 0; i--) {
for (int j = 0; j < arr[i]; j++)
if (arr[i + 1] != 6 || j != 2)
ans += dp[i][j];
if (arr[i] == 4 || (arr[i + 1] == 6 && arr[i] == 2))
break;
}
return ans;
}
int main() {
// freopen("a.in","r",stdin);
// freopen("k.out","w",stdout);
init();
long long a, b;
while (scanf("%lld %lld", &a, &b) != EOF && a && b) printf("%lld\n", solve(b + 1) - solve(a));
return 0;
}