HDU 2089 不要62 数位DP

发表于 |

这条题目是典型的求[L, R]区间内满足某性质的整数的数目问题，通常解法是用[0, R]区间的数目减去[0, L-1]区间的数目。数位DP是此类问题常见的解题思路。

数位DP模板

数位dp其实类似于中记忆化搜索。数位DP由最深$N$（$N$为$R$的十进制位数）层dfs组成。出于实现方便，数字$123$映射到int nums[]数组中，首尾颠倒变成$[3, 2, 1]$。由于从原数字的最高位往最末位递归，因此记忆化搜索的每次递归pos是从$N-1$递减的。

1
2
3
4
5
6
7
8
9
10
11
12
LL solve(int x){
	memset(nums, 0, sizeof nums);
	memset(dp, -1, sizeof dp);
	int ppos = 0;
	while (x != 0) {
		nums[ppos++] = x % 10;
		x /= 10;
	}
	// 开始dfs记忆化搜索
	LL ans = dfs(ppos - 1, 0, true);
	return ans;
}

flag表示在遍历当前pos位时，比pos位低的$[0..pos-1]$位是否有限制，其初始值为true，因为最高位肯定是有限制的。例如数字$234$，在遍历到$cur[2]$为$1$时，$cur[2..1]$能够取遍$[10..19]$，但是当$cur[2]$为能取的上确界$2$时，低位的$cur[1]$只能够在$[0..nums[1]]$的范围里面取了，$cur[2..1]$取值为$[21..23]$。总结规律，只有前缀$[pos+1 .. N-1]$的flag为true（前缀的所有位都取到了上确界），且当前位pos的当前值$cur[pos]$也取上确界$nums[pos]$或$9$时，低位$cur[pos-1]$只能取$[0..nums[pos-1]]$，否则能自由取$[0..9]$。status用来表示状态，这个状态被用来计算当前子问题的结果，例如在这道题目中，status用来记录是否存在62或者4。

子结构一般为$dp[pos][..]..$的多维数组。后面的几维与状态有关，有时候可能还需要进行离散化。从上面可知当flag为true的时候，不能取满$[0..9]$，此时我们就没必要记录下结果，因为显然取满的情况是占绝大多数的。因此dfs的结构如下

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
LL dfs(int pos, int status, bool flag) {
	if (pos == -1) {
		// 如果到达最深层，check是否继续满足题目中的性质
		return check(status) ? 1 : 0;
	}
	if (!flag && dp[pos][status] != -1) {
		// 如果此层能够取满，那查看能不能复用存储的结果
		return dp[pos][status];
	}
	LL ans = 0;
	int end = flag ? nums[pos] : 9; // 如果flag为true就是不自由的，end只能取到nums[pos]
	for (int i = 0; i <= end; i++)
	{
		int newstatus = ...;
		// 如果最终结果与前缀的结果满足and或者or的性质，这里还可以剪枝
		bool newflag = flag && (i == end); // 下一层的flag，注意要满足两个条件才会有限制
		ans += dfs(pos - 1, newstatus, newflag);
	}
	if (!flag)
	{
		// 只保存任何层取满[0..9]的结果
		dp[pos][status] = ans;
	}
	return ans;
}

题解

AC代码