bzoj 1026 windy数(数位dp入门题)

题目链接
题意:不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?
思路:数位dp
这道题的特点是前面不允许前导0,也就是说,如果第i位前面全是0的话,这个数就变成了i位数,i就变成了最高位,而最高位没有前面的数(如果这里不考虑不允许前导0这个因素而把前面的一个数认为成是0就错了) 最高位的数可以直接取。 还有记忆化调用以及存储的时候也要注意…只有当位数相同的时候转移才有意义。 具体的方法是dfs中多了一个prehasnonzero的bool变量,就是字面意思,判断当前位置前面的位置是够存在一个非0的值。

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz