U534161 开学酒局（数位dp 模板）

$\qquad\!\!$开学的前一天，LHRG李 的几位兄弟邀请他来喝酒一聚，由于 LHRG李 的酒量很差，喝了几杯之后就连连摆手。但是他热情的兄弟却连连灌他，直到看到他实在喝不下了，便让他做一道题，看看 LHRG李 是否还清醒。LHRG李 已经不清醒了，但是好兄弟们一旦看到 LHRG李 出现问题，就要把他送去医院。 LHRG李不想去医院，所以他找到了你。

$\qquad\!\!$LHRG李 交给你的问题是：从 $l$ 到 $r$（包括 $l$ 和 $r$）不含前导零的数字中，有多少个数字，**对于每连续的三个数位上的数字，较高的两个数位上的数字之差的绝对值与第三个数位上的数字之差的绝对值小于 $k$**？ $\qquad\!\!$时间紧急，任务量大，你的程序只有 $0.2s$ 的思考时间。

一行，两个正整数：$l,r,k$。

一个正整数，符合条件的数字的个数。

数据范围： | 子任务 | 测试点编号 | 总分数 | 数据范围 | | :----: | :----: | :----: | :----: | | **Subtask #1** | $1-3$ | 10 | $100\leqslant l \leqslant r \leqslant 200$ | | **Subtask #2** | $6-9$ | 20 | $100\leqslant l \leqslant r \leqslant 2000$ | | **Subtask #3** | $10-18$ | 20 | $100\leqslant l \leqslant r \leqslant 2\times10^6$ | | **Subtask #4** | $19-21$ | 10 | $100\leqslant l \leqslant r \leqslant 2\times10^9,k=1$ | | **Subtask #5** | $22-30$ | 40 | $100\leqslant l \leqslant r \leqslant 2\times10^9,1\leqslant k \leqslant 10$ | 对于 $100\%$ 的数据，$100\leqslant l \leqslant r \leqslant 2\times10^9,1\leqslant k \leqslant 10$ **友情提示：注意时间限制！** **计分规则：** $\qquad\!\!$对于每个 subtask，假设其中共有 $3k$ 个测试点，未 $AC$ 数量为 $x$。 $\qquad\!\!$$x=0$ 时，得 $10k$ 分；$x\leqslant k$ 时，得 $10k-4x$ 分；$x>k$ 时，得 $6k-3(x-k)$ 分。 $\qquad\!\!$[计分脚本](http://lhrg.github.io/开学酒局subtask计分脚本/) [题解](http://lhrg.github.io/题解-U534161-【开学酒局】/) ------------------------- 出题者：LHRG李