CF620B Grandfather Dovlet’s calculator 题解

· · 题解

思路

这道题和 P4999 有点类似，把数字的贡献变一下即可，每个数字的贡献如下：

v[10]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

然后我们就可以用数位 dp 来水这道题了。

要注意的是本题的前导零会影响结果（ 0 也有贡献）。

数位 dp 简述

数位 dp 是解决某区间内求特定数数量的算法。

在暴力枚举数位找数的基础上，加上数组进行记忆化。举个栗子， 1234 和 2234 的贡献除了最高位 1 和 2 其余的 234 是一样的，所以我们就可以开个数组记录后面位数的贡献。这就是数位 dp 的核心思想。

对于本题，我们先分解数位到数组里，然后一位一位的

代码

#include <cstdio>
#include <cstring>
#include <cmath>

#define N 30

using namespace IO;

int v[10]={6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
ll f[N][N*9];//记忆化数组
int bit[N];//数位

int init(ll x) {//分解数位
    int cnt=0;
    memset(f, -1, sizeof(f));
    while(x)
        bit[++cnt]=x%10, x/=10;
    return cnt;
}
ll dfs(int pos, ll x, bool flag, bool zer) { // pos 指总共的数位， x 表示当前所处理的数， flag 表示是否“贴着放”
    if(!pos) {//递归边界
        return x;
    }
    if(!flag && !zer && f[pos][x]!=-1) {//记忆化
        return f[pos][x];
    }
    int mx=flag? bit[pos]:9;
    ll ans=0;
    for(int i=0; i<=mx; i++) {
        if(zer && !i)//前导零的处理
            ans+=dfs(pos-1, 0, flag&&i==mx, 1);//注意参数的第二位不要取负数，不然会错得很惨
        else
            ans+=dfs(pos-1, x+v[i], flag&&i==mx, 0);//加上新来的数的贡献
    }
    if(!flag && !zer)
        f[pos][x]=ans;//记忆化
    return ans;
}
ll dp(ll x) {
    return dfs(init(x), 0, 1, 1);
}

int main() {
    ll l, r;
    scanf("%d%d", &l, &r);
    printf("%d", dp(r)-dp(l-1));
    puts("");
    return 0;
}