P2657 [SCOI2009] windy 数 & 简单数位 DP

· · 个人记录

数位 DP 的状态模板是设 f(i, j) 表示第 i 位，限制为 j 时的方案数量。其中，j = 1 表示有限制，即这一位上最大为 x_i；否则，这一位上最大为 9。

本题在简单数位 DP 的基础上，还加了一个条件：两数相差至少为 2。

这时候，朴素状态显然无法保证这一条件。那么我们加一维度，设 f(i, j, k) 表示第 i 位，限制为 j，且这一位为 k 时候的方案数量。那么我们就能得出一个明显的转移，懒得 \LaTeX 了。

但是有一个问题：考虑前导零。如果我们就用上面的方式转移的话，很明显这会出错，因为 1 不会被考虑在内。这时候，我们可以手动处理一下特殊情况：将前导零的情况特判，然后再转移即可。

btw 数位 DP 这种东西好恶心）