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]$的flagtrue(前缀的所有位都取到了上确界),当前位pos的当前值$cur[pos]$也取上确界$nums[pos]$或$9$时,低位$cur[pos-1]$只能取$[0..nums[pos-1]]$,否则能自由取$[0..9]$。status用来表示状态,例如在这道题目中,status用来记录是否存在62或者4。

子结构一般为$dp[pos][..]..$的多维数组。后面的几维与状态有关,有时候可能还需要进行离散化。从上面可知当flagtrue的时候,不能取满$[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代码