LibreOJ 2044 「CQOI2016」手机号码

发表于 | 分类于 |

这题其实不难，是数位 DP 里边状态相对码农的类型。

DP 时除了模板以外，记录上上位，是否出现过 \(4/8\)，是否出现过连续的三个同号。
然后按照套路走。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 11;
long long l,r;
int d[LEN + 5],tot;
long long f[LEN + 5][10][10][2][2][2][2];
long long dfs(int x,int num,int pre,int lead,int yes,int _4,int _8,int top)
{
    if(!x)
        return yes;
    if(!top && ~f[x][num][pre][lead][yes][_4][_8])
        return f[x][num][pre][lead][yes][_4][_8];
    long long ret = 0;
    int bound = top ? d[x] : 9;
    for(register int i = 0;i <= bound;++i)
    {
        if((_4 && i == 8) || (_8 && i == 4))
            continue;
        ret += dfs(x - 1,i,num,lead && !i,yes || (!lead && num == pre && i == num),_4 || (i == 4),_8 || (i == 8),top && i == bound);
    }
    if(!top)
        f[x][num][pre][lead][yes][_4][_8] = ret;
    return ret;
}
long long solve(long long x)
{
    memset(f,-1,sizeof f) ;
    tot = 0;
    while(x)
    {
        d[++tot] = x % 10;
        x /= 10;
    }
    return dfs(tot,0,0,1,0,0,0,1);
}
int main()
{
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",solve(r) - solve(l - 1));
}