HDU - 2089 不要62（数位DP）

题目如下：

杭州人称那些傻乎乎粘嗒嗒的人为 $62$（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有 $4$ 或 $62$ 的号码。例如：
$623157341888914$
都属于不吉利号码。但是，$61152$ 虽然含有 $6$ 和 $2$ ，但不是 $62$ 连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对 $n、m（0<n\le m<1000000）$，如果遇到都是 $0$ 的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample

Input

1 100
0 0

Output

80

题目链接

题解 or 思路：

数位DP
dfs(位置， 是否有限制， 上一位是否是 $6$ )
具体请参考下面的代码。

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \ios::sync_with_stdio(false); \cin.tie(0);
// #define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 1000009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int l, r, f[N][2];
int a[N], idx;
int dfs(int pos, bool lim, bool sex)
{if (pos == 0)return 1;if (!lim && f[pos][sex] != -1)return f[pos][sex];int len = lim ? a[pos] : 9;int ans = 0;for (int i = 0; i <= len; i++){if (i == 4)	continue;if (i == 2 && sex)	continue;ans += dfs(pos - 1, lim && i == a[pos], i == 6);}if (!lim)f[pos][sex] = ans;return ans;
}
int work(int x)
{idx = 0;while (x){a[++idx] = x % 10;x /= 10;}return dfs(idx, 1, 0);
}
void solve()
{int x = work(l - 1), y = work(r);cout << y - x << '\n';
}
int main()
{buff;memset(f, -1, sizeof f);int _ = 1;// cin >> _;while (cin >> l >> r, l, r)solve();
}