HDU 2089 不要62（数位DP，DFS写法）

HDU 2089 不要62

---

$cal$函数（一般情况）：

注意每次初始化 $DP$ 数组为 $-1$，长度 $len=0$

---

基本参数：

$len:$ 数位长度，一般根据这个来确定数组范围

$a_i:$ 每个数位具体数字
返回值 $return$ 根据题目的初始条件来确定前导 $0$ 以及 $pre$

---

DFS 函数（一般情况）：

变量 $res$ 来记录答案，初始化一般为 $0$
变量 $up$ 表示能枚举的最高位数
采用记忆化搜索的方式：
if (!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];

只有无限制、无前导零才算，不然都是未搜索完的情况。

return limit ? res : dp[pos][pre] = res;

如果最后还有限制，那么返回 res，否则返回 dp[pos][pre]

---

基本参数：

假设数字 $x$ 位数为 $a_1\cdots a_n$

---

必填参数：

$pos:$ 表示数字的位数

从末位或第一位开始，要根据题目的数字构造性质来选择顺序，一般选择从 $a_1$ 到 $a_n$ 的顺序。初始从 $len$ 开始的话，边界条件应该是 $pos=0$，限制位数应该是 $a_{pos}$，DFS 时 $pos-1$ ；初始从 $1$ 开始的话，边界条件应该是 $pos>len$ ，限制位数应该是 $a_{len-pos+1}$，$DFS$ 时 $pos+1$。两种都可以，看个人习惯。

$limit:$ 可以填数的限制（无限制的话 $(limit=0)$ $0\sim 9$ 随便填，否则只能填到 $a_i$）

如果搜索到 $a_1\cdots a_{pos}\cdots a_n$，原数位为 $a_1\cdots a_k\cdots a_n$，那么我们必须对接下来搜索的数加以限制，也就是不能超过区间右端点 $R$，所以要引入 $limit$ 这个参数，如果 $limit=1$，那么最高位数 $up\le a_{pos+1}$，如果没有限制，那么 $up=9$（十进制下）这也就是确定搜索位数上界的语句 limit ? a[pos] : 9;
如果 $limit=1$ 且已经取到了能取到的最高位时 $(a_{pos}=a_k)$，那么下一个 $limit=1$
如果 $limit=1$ 且没有取到能取到的最高位时 $(a_{pos}<a_k)$，那么下一个 $limit=0$
如果 $limit=0$，那么下一个 $limit=0$，因为前一位没有限制后一位必定没有限制。
所以我们可以把这 $3$ 种情况合成一个语句进行下一次搜索：limit && i == up$(i$为当前枚举的数字$)$

---

可选参数：

$pre:$ 表示上一个数是多少

有些题目会用到前面的数

$lead:$ 前导零是否存在，$lead=1$ 存在前导零，否则不存在。

一般来说有些题目不加限制前导零会影响数字结构，所以 $lead$ 是一个很重要的参数。
如果 $lead=1$ 且当前位为 $0$，那么说明当前位是前导 $0$，继续搜索 $pos+1$，其他条件不变。
如果 $lead=1$ 且当前位不为 $0$，那么说明当前位是最高位，继续搜索 $pos+1$，条件变动。
如果 $lead=0$，则不需要操作。

$sum:$ 搜索到当前所有数字之和

有些题目会出现数字之和的条件

$cnt:$ 某个数字出现的次数

有些题目会出现某个数字出现次数的条件

参数基本的差不多这些，有些较难题目会用到更多方法或改变$\text{DP}$状态

#include 
using namespace std;

const int N = 11;
int l, r, len, a[N], dp[N][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 (i == 4 || (i == 2 && pre == 6)) 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);
	len = 0;
	while (x) a[++ len] = x % 10, x /= 10;
	return dfs(len, 0, 1);
}

int main() {
	while (cin >> l >> r, l || r) {
		cout << cal(r) - cal(l - 1) << endl;
	}
	return 0;
}
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