HDU - 2089- 不要62 · znzryb
## 思路讲解
[](https://www.notion.so/1724539447bd80b4a60cfaf6e78e5b35) 我们看看可不可以一题多解，用数位dp解一下这道
主要就是记忆化搜索，具体看黑书还有我的代码注释，还是比较详细的
黑书还是好，让我仿写，但还可以留白一部分，让我自己写，真是对我太友好了
## AC代码
[https://vjudge.net/solution/57465304](https://vjudge.net/solution/57465304)
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;
// dp表示第i位符合要求的数字数量,比如dp[1]=9，因为除了4都满足
ll L,R,dp[15][3],digit[15];
// digit是指该数的第i位为几，比如说342，digit[1]=2
// 上一位是不是6？
ll dfs(ll len,bool isMax,bool is6){
if(len==0)// 递归结束条件
return 1;
// 记忆化结束条件
if(dp[len][is6]!=-1 && isMax==false)
return dp[len][is6];
ll res=0,maxx;
// 如果不是最大位，那么就直接取9
maxx= isMax ? digit[len]:9;
for(int i=0;i<=maxx;++i){
// 记忆化搜索关键部分来了，数位dp之所以可以这样
// 是因为 最高位+后面的数=新数
if(i==4) // 排除4
continue;
if(is6 && i==2) // 不能组成62
continue;
if(i==6){
res+=dfs(len-1,isMax && i==maxx,true);
}else{
// 如果前数进入是最大数，i也是最大数，后面的也要受限制
// 比如324，百位为3确定了，十位最多为2
// 但如果324，百位为2确定了，后面的数想写啥写啥
res+=dfs(len-1,isMax && i==maxx,false);
}
}
if(!isMax)
dp[len][is6]=res;
return res;
}
void solve(){
memset(dp, -1, sizeof(dp));
string Ls=to_string(L-1);
for(int i=1;i<=Ls.size();++i){
digit[i]=Ls[Ls.size()-i]-'0';
}
ll lres=dfs(Ls.size(), true,false);
string Rs=to_string(R);
for(int i=1;i<=Rs.size();++i){
digit[i]=Rs[Rs.size()-i]-'0';
}
ll rres=dfs(Rs.size(), true,false);
cout<<rres-lres<<'\n';
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
while (cin>>L>>R) {
if(L==0 && R==0)
break;
solve();
}
return 0;
}
// AC https://vjudge.net/solution/57465304
```
## 心路历程（WA，TLE，MLE……）