[CQOI2016]手机号码

用来数位DP入门，数位DP把当前是否需要限制取数范围（是否正在贴着临界值跑，即下面的limited）和一切需要满足的条件全部塞进记忆化搜索参数里面就好了，具体情况转移便好了，答案为\(work(R)-work(L-1)\)

#include 
    
     #include 
     
      #define DP dp[p][a][b][hav_same][hav8][hav4][limited]#define ll long longusing namespace std;ll dp[14][11][11][2][2][2][2];int num[14];ll solve(int p, int a, int b, bool hav_same, bool hav8, bool hav4, bool limited){    //当前第p位，前2位为a，前1位为b，hav_same:是否有三个连续相等的，hav_8,hav_4：是否存在数字8\4，是否限制取数范围    if(hav4&&hav8) return 0;    if(p<=0) return hav_same;    if(DP!=-1) return DP;    ll ans=0;    int maxnum=(limited?num[p]:9);    for(int i=0;i<=maxnum;++i)        ans+=solve(p-1, b, i, hav_same||(i==a&&i==b), hav8||(i==8), hav4||(i==4), limited&&(i==maxnum));    return DP=ans;}ll work(ll x){    if(x<1e10) return 0;    memset(dp, -1, sizeof(dp));    int len;    for(len=0;x;x/=10) num[++len]=x%10;    ll ans=0;    for(int i=num[len];i>=1;--i)        ans+=solve(11-1, -1, i, 0, i==8, i==4, i==num[len]);    return ans;}int main(){    ll l,r;    scanf("%lld %lld", &l, &r);    printf("%lld\n", work(r)-work(l-1));    return 0;}