数位 dp 写法

众所周知，数位 dp 是一种难写难调的 sb dp，这里记录一种便于调试的写法。

1. 对于一个区间询问 \([a,b]\)，可以把它拆分成 \([1,b]\) 和 \([1,a-1]\) 两个部分作差，并使用函数 \(solve(x)\) 计算出 \([1,x]\) 的答案，将答案的形式改写为 \(solve(b)-solve(a-1)\) 以减小码量；
2. 对于状态转移与答案输出，使用记忆化搜索，其明显简单于直接循环 dp；
3. 对于一个数的表示，直接用 vector 存储也许会方便很多。

示例代码：

// 题目名称：不要 62
int dfs(int x, int lst, bool op)
// x 表示当前枚举位置，lst 表示上一个数，op 表示该数是否有限制
{
	if (!x) return 1;
	if (!op && ~dp[x][lst]) return dp[x][lst];

	int mx = op ? num[x] : 9, tot = 0;
	rep(i, 0, mx) {
		if (i == 4) continue;
		if (lst == 6 && i == 2) continue;
		tot += dfs(x - 1, i, op && i == mx);
	}

	if (!op) dp[x][lst] = tot;
	return tot;
}

int solve(int x)
{
	num.clear();
	num.emplace_back(-1); // 空位置
	while (x) num.emplace_back(x % 10), x /= 10;
	return dfs(num.size() - 1, 0, 1);
}

本篇博客只讲了写法，只因我是一个鸽子（咕咕咕）。。。