bzoj4521

数位dp

复习数位dp

数位dp一般用记忆化搜索来解决

观察需要满足的条件，然后计入状态

状态还要记录是否达到上线，以及前导零

比如说这道题

dfs(bit,a4,a8,cnt,last,limit)

由于这道题枚举的时候不可能有前导零，所以就不记录前导零

bit表示当前考虑第bit位，从高到低

a4表示是否有4

a8表示是否有8

cnt记录最多连续出现次数，最大为3，limit记录是否卡上界

枚举这位选什么，如果卡上界，那么从0->st[bit],否则从0->9

然后判断状态是否更改

如果不卡上界记忆化

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

ll l, r;

int top;

int st[];

ll dp[][][][];

ll dfs(int bit, int a4, int a8, int cnt, int last, int limit)

{

    if((a4 & a8)) return ;

    if(bit == ) return cnt == ;

    if(!limit && dp[bit][a4][a8][cnt] != -) return dp[bit][a4][a8][cnt];

    ll ret = ;

    int lim = limit ? st[bit] : ;

    for(int i = bit == top ?  : ; i <= lim; ++i)

    {

        if(cnt == ) ret += dfs(bit - , a4 || i == , a8 || i == , , i, limit && i == st[bit]);

        else ret += dfs(bit - , a4 || i == , a8 || i == , i == last ? cnt +  : , i, limit && i == st[bit]);

    }

    return limit ? ret : dp[bit][a4][a8][cnt] = ret;

}

ll solve(ll n)

{

    if(n == 1e10 - ) return ;

    top = ;

    while(n)

    {

        st[++top] = n % ;

        n /= ;

    }

    return dfs(top, , , , -, );

}

int main()

{

    memset(dp, -, sizeof(dp));

    scanf("%lld%lld", &l, &r);

    printf("%lld\n", solve(r) - solve(l - ));

    return ;

}