P4124手机号码数位dp记忆化搜索70分

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
ll a, b;
int dp[20][2][2][10][10];//长度 8 4 前 相同
int dig[20];
int cnt = 0;
int dfs(int len, bool _8, bool _4, int pre, int same, bool flag)//长度 8 4 前 相同个数 是否dig
{
    if(!len) return !(_8&_4) && same==3;
    if(!flag&&~dp[len][_8][_4][pre][same]) return dp[len][_8][_4][pre][same];

    int up = flag?dig[len]:9;
    int ret = 0;
    for (int i=len==cnt;i<=up;++i)
    {
        if(!same) ret += dfs(len-1, _8||i==8, _4||i==4, i, 1, flag&&i==up);
        else ret += dfs(len-1, _8||i==8, _4||i==4, i, (same==3?same:(i==pre?same+1:1)), flag&&i==up);
    }
    if(!flag) dp[len][_8][_4][pre][same] = ret;
    return ret;
}
int solve(int x)
{
    cnt=0;
    while(x)
    {
        dig[++cnt] = x%10;
        x/=10;
    }
    return dfs(cnt, 0, 0, 0, 0, 1);
}
signed main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%lld%lld", &a, &b);
    printf("%lld", solve(b) - solve(a-1));
    return 0;
}