BZOJ 1026 [SCOI2009]windy 数

发布于 2017-08-24  155 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1026

题意:定义一种 windy 数。不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。在 A 和 B 之间,包括 A 和 B,总共有多少个 windy 数?


人生中的第一次数位 dp...

套路大概是这样的:首先预处理出长度为 i 位的,首位为 j 的 windy 数的个数。

然后考虑怎么求 1~n 的 windy 数,令 n 长 len 位

①:对于第一次考虑,长度在 1~len-1 位的 windy 数一定都合法,直接统计进答案中。

②:此后,对于每次考虑,长度在 len 位但是首位小于 n 的首位的 windy 数也都可以统计进答案中。

③:然后,我们 钦定 首位为 n 的首位,这样问题的规模就缩小了,对于去掉 n 的首位得到的数 m,递归步骤②

不过直接写递归的效率是不太妙的... 所以写了迭代版,不过貌似递归版更好理解?

 


一个非常弱的准退役OIER