bzoj 4521 [Cqoi2016]手机号码——数位dp

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4521

dfs真好用~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=15;
int dg[N];
ll l,r,dp[N][5][N][2][2][2];
ll dfs(int p,int len,int lst,bool p0,bool p1,bool ok,bool fx)
{
    if(!p){return ok&(!(p0&p1));}
    if(!fx&&dp[p][len][lst][p0][p1][ok]!=-1)return dp[p][len][lst][p0][p1][ok];
    int st=0;if(p==11)st=1;
    int end=9;if(fx)end=dg[p];
    ll ret=0;
    for(int i=st;i<=end;i++)
    {
        int lenn=1;if(i==lst)lenn=len+1;
        if(lenn>3)lenn=3;
        ret+=dfs(p-1,lenn,i,p0|(i==4),p1|(i==8),ok|(lenn==3),fx&(i==dg[p]));
    }
    if(!fx)dp[p][len][lst][p0][p1][ok]=ret;
    return ret;
}
ll calc(ll x)
{
    if(x<1e10)return 0;
    for(int i=1;i<=11;i++)dg[i]=x%10,x/=10;
    memset(dp,-1,sizeof dp);
    return dfs(11,0,0,0,0,0,1);
}
int main()
{
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",calc(r)-calc(l-1));
    return 0;
}