题目描述
“非常的新鲜,非常的美味”,这是我修院对美食的极大赞赏。
如何定义一道美食为美味呢,我塔子百思不得其解,我修院解释道:假设一道美食有一个美味值,当且仅当它的相邻数位都不相同。例如:114514是不美味的,但1919810则美味的很呐!
思路:数位DP
定义dp(i,mask,isLimit,isNum)表示构造第i位及其之后的数位的合法方案数
- mask表示前面选过的数字集合,换句话说,第i位要选的数字不能出现在mask中
- isLimit表示当前是否受到了n的约束。若为真,则第i位填入的数字至多为 s[i],否则可以是9
- isNum表示i前面是否填了数字,若为假,则当前位可以跳过(不填数字),或者要填入的数字至少为 1(不允许出现前导0);若为真,则要填入的数字可以从 0 开始。