数位DP get ！

A4paper · 2018-11-01 15:01:45 · 个人记录

数位 DP 一般应用于：

1. 求出在给定区间[A,B]内，符合条件P(i)的数i的个数。

2. 条件P(i)一般与数的大小无关，而与 数的组成 有关。

先来举个例子：

求区间 [a,b] 中不含 49 的数的个数 (2<a,b<2*10^9)

可以发现， a,b 的范围很大，直接暴力会 T 飞，所以考虑 DP

我们可以枚举每一位进行统计，然后利用类似前缀和的形式给出答案。

记 f[i][1/0] 表示在第 i 位是 4(1) 不是(0) 的合法数字的个数

code:

int a,b,digital[20],f[20][2];
//digital用于将a,b的每一位拆开存
int dfs(int len, bool if4, bool limit)
{//len为当前是第几位，if4表示上一位是不是4，
 //limit表示之前的数位有没有全部达到上限
    if(len == 0) return 1;
    if(!limit && f[len][if4]) return f[len][if4];
    int ans = 0;
    int maxx = (limit ? digital[len] : 9);
    //如果之前的数位都达到上限了，那这一位就有了限制。
    //比如数字1234，当前搜到了123x，那x最大到4，
    //如果只搜到了122x，那x可以取1~10
    for(int i=0;i<=maxx;i++)
    {
        if(if4 && i==9) continue;
        //上一位为4，而这一位是9，就不合法了。
        ans += dfs(len-1,i==4,limit&&i==maxx);
    }
    return limit ? ans : f[len][if4]=ans;
    //如果没达到限制，转移f的状态，否则不转移。
    //比如数字1234，当前搜到123x，那x的答案数就不能存到f[1]里，
    //如果只搜到122x，x可以取1~10，所以f[1]的值就是x的答案
}

int solve(int x)
{
    int cnt = 0;
    while(x)
    {
        digital[++cnt] = x%10;
        x /= 10;
    }
    return dfs(cnt,0,1);
}

int main(void)
{
    cin >> a >> b;
    cout << solve(b)-solve(a-1);
    return 0;
}

模板：

传送门

这是一道模板题，重点在于前导零的处理：

首先要知道的是，当首位为 0 时，第二位可以选任何数，因为此时的第二位相当于第一位，但此时的状态不能计入 f 数组，因为数字的第一位不可能为 0 ，所以它不属于当前状态。

对于有前导零的转移，可以记一个参数 leading\_zero 表示当前数位之前是不是全为 0 ，如果 leading\_zreo = 1 并且当前位的数 i = 0，那么它的下一位可以选任何数，所以 last 记为 -2 即可。

对了，还是说一下 dfs 中的参数吧：