数位DP

引入

给你数字l、r，求l到r之间有多少个数

弱智题？

方法一

从 $l$ 开始，暴力枚举到 $r$ , 时间 $\Theta(n)$

方法二

公式， $ans = r - l + 1$

方法三

$ans = res(r) - res(l - 1)$
$res$ 如何求？
$\Huge \text{数位dp！！！}$

核心思想：按字典序由高位到低位计算

看图

-	4	3	2	1	0
-	6	5	6	4	3
0
1
2
3
4
5
6
…

求 $0$ 到 $65643$ 中有多少个小于 $65643$

计算第 $4$ 位：

-	4	3	2	1	0
-	6	5	6	4	3
0	$10^4$
1	$10^4$
2	$10^4$
3	$10^4$
4	$10^4$
5	$10^4$
6	?
…

我们发现，第 $4$ 位取 $6$，不能直接确定，因此继续算（注：第 $4$ 位取 $1$ 到 $5$ 时，方案数已确定，因此表中下一列的方案数和是上一列最后一种情况的方案数）

-	4	3	2	1	0
-	6	5	6	4	3
0	$10^4$	$10^3$
1	$10^4$	$10^3$
2	$10^4$	$10^3$
3	$10^4$	$10^3$
4	$10^4$	$10^3$
5	$10^4$	？
6	$\nearrow$
…

同上，可继续推出整表

-	4	3	2	1	0
-	6	5	6	4	3
0	$10^4$	$10^3$	$10^2$	$10^1$	$10^0$
1	$10^4$	$10^3$	$10^2$	$10^1$	$10^0$
2	$10^4$	$10^3$	$10^2$	$10^1$	$10^0$
3	$10^4$	$10^3$	$10^2$	$10^1$	$10^0$
4	$10^4$	$10^3$	$10^2$	$\nearrow$
5	$10^4$	$\searrow$	$10^2$
6	$\nearrow$		$\nearrow$
…

易得，答案为 $5 \times 10 ^ 4 + 4 \times 10 ^ 3 + 5 \times 10 ^ 2 + 4 \times 10 ^ 1 + 4 \times 10 ^ 0$

这就是数位dp的思想

模板

int dp[N][N], a[N];

int dfs(int pos, int pre, bool lead, bool limit) {//pos：当前一位  pre：前一位传下来用于判断或计算的参数  lead：前导零（因题可适当取舍）  limit：是否有限制（即上一位是否为那位最大上界） 
    if (!pos) return 1;//求和返回pre 
    if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
    // 无lead 5: if (!limit && dp[pos][pre] != -1) return dp[pos][pre];
    int res = 0, up = limit ? a[pos] : 最大上界;
    for (int i = 0; i <= up; i ++) {
        if ( 不满足条件 ) continue;
        if(lead && !i)
        	res += dfs(pos - 1, 因题而异, lead && !i, limit && i == up);
        else
        	res += dfs(pos - 1, 因题而异, lead && !i, limit && i == up);
        // 无lead 10 ~ 13: res += dfs(pos - 1, 因题而异, limit && i == up);
    }
    return limit ? res : (lead ? res : dp[pos][pre] = res);
    // 无lead 16:  return limit ? res : dp[pos][pre] = res;
}
int cal(int x) {
    memset(dp, -1, sizeof dp);
    int len = 0;
    while (x) a[++ len] = x % 进制, x /= 进制;
    return dfs(len, 因题而异, 1, 1);
}

例题

AcWing 1082. 数字游戏

没啥好说，直接套

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int dp[N][N], a[N];

int dfs(int pos, int pre, bool limit)
{
	if(!pos) return 1;
	if(!limit && dp[pos][pre] != -1) return dp[pos][pre];
	int res = 0, up = limit ? a[pos] : 9;
	for(int i = 0; i <= up; i ++)
	{
		if(i < pre) continue;
		res += dfs(pos - 1, i, limit && i == up);
	}
	return limit ? res : dp[pos][pre] = res;
}

int cal(int x)
{
	memset(dp, -1, sizeof dp);
	int len = 0;
	while(x) a[++ len] = x % 10, x /= 10;
	return dfs(len, 0, 1);
}

int main()
{
	int l, r;
	while(cin >> l >> r) cout << cal(r) - cal(l - 1);
}

AcWing 1083. Windy数

直接套+1

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int dp[N][N], a[N];

int dfs(int pos, int pre, bool lead, bool limit) {
    if (!pos) return 1;
    if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
    int res = 0, up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; i ++) {
        if (abs(pre - i) < 2) continue;
        if(lead && !i)
        	res += dfs(pos - 1, -2, lead && !i, limit && i == up);
        else
        	res += dfs(pos - 1, i, lead && !i, limit && i == up);
    }
    return limit ? res : (lead ? res : dp[pos][pre] = res);
}
int cal(int x) {
    memset(dp, -1, sizeof dp);
    int len = 0;
    while (x) a[++ len] = x % 10, x /= 10;
    return dfs(len, -2, 1, 1);
}
signed main() {
	int l, r;
    cin >> l >> r;
    cout << cal(r) - cal(l - 1) << endl;
}

AcWing 1085. 不要62

直接套，但是有两个判断条件

#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int dp[N][N], a[N];

int dfs(int pos, int pre, int limit)
{
	if(!pos) return 1;
	if(!limit && dp[pos][pre] != -1) return dp[pos][pre];
	int res = 0, up = limit ? a[pos] : 9;
	for(int i = 0; i <= up; i ++)
	{
		if(pre == 6 && i == 2 || i == 4) continue;
		res += dfs(pos - 1, i, limit && i == up);
	}
	return limit ? res : dp[pos][pre] = res;
}

int cal(int x)
{
	memset(dp, -1, sizeof dp);
	int len = 0;
	while(x) a[++ len] = x % 10, x /= 10;
	return dfs(len, 0, 1);
}

int main()
{
	int l, r;
	while(cin >> l >> r && l && r) cout << cal(r) - cal(l - 1) << "\n";
}