Digit DP
经典题型¶
数位 DP 问题往往都是这样的题型，给定一个闭区间 ，让你求这个区间中满足 某种条件 的数的总数。
例题 SCOI2009 windy 数
题目大意：给定一个区间 ，求其中满足条件 不含前导 且相邻两个数字相差至少为 的数字个数。
首先我们将问题转化成更加简单的形式。设 表示在区间 中满足条件的数的数量，那么所求的答案就是 。
分开求解这两个问题。
对于一个小于 的数，它从高到低肯定出现某一位，使得这一位上的数值小于 这一位上对应的数值。而之前的所有位都和 上的位相等。
有了这个性质，我们可以定义 表示当前将要考虑的是从高到低的第 位，当前该前缀的状态为 且前缀和当前求解的数字的大小关系是 （ 表示等于， 表示小于）时的数字个数。在本题中，这个前缀的状态就是上一位的值，因为当前将要确定的位不能取哪些数只和上一位有关。在其他题目中，这个值可以是：前缀的数字和，前缀所有数字的 ，该前缀取模某个数的余数，也有两种或多种合用的情况。
写出 状态转移方程：
这里的 就是当前枚举的下一位的值，而 就是当前能取到的最高位。因为如果 ，那么你在这一位上取的值一定不能大于求解的数字上该位的值，否则则没有限制。
我们发现，尽管前缀所选择的状态不同，而 的三个参数相同，答案就是一样的。为了防止这个答案被计算多次，可以使用记忆化搜索的方式实现。
核心代码：
int dfs(int x, int st, int op) // op=1 =;op=0 <
{
if (!x) return 1;
if (!op && ~f[x][st]) return f[x][st];
int maxx = op ? dim[x] : 9, ret = 0;
for (int i = 0; i <= maxx; i++) {
if (abs(st - i) < 2) continue;
if (st == 11 && i == 0)
ret += dfs(x - 1, 11, op & (i == maxx));
else
ret += dfs(x - 1, i, op & (i == maxx));
}
if (!op) f[x][st] = ret;
return ret;
}
int solve(int x) {
memset(f, -1, sizeof f);
dim.clear();
dim.push_back(-1);
int t = x;
while (x) {
dim.push_back(x % 10);
x /= 10;
}
return dfs(dim.size() - 1, 11, 1);
}几道练习题¶
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.