题目描述
Windy 定义了一种 Windy 数:不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 Windy 数。
Windy 想知道,在 $A$ 和 $B$ 之间,包括 $A$ 和 $B$,总共有多少个 Windy 数?
输入格式
共一行,包含两个整数 $A$ 和 $B$。
输出格式
输出一个整数,表示答案。
数据范围
$1 \le A \le B \le 2 \times 10^9$
输入样例1:
1 10
输出样例1:
9
输入样例2:
25 50
输出样例2:
20
C++ 代码
/*
记忆化搜索:
(从高位往低位填)
f[i][j] 表示的是还剩 i 位数要填, 且上一次填的是 j 的所有合法 Windy 数
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 18, M = 10;
int l, r;
int f[N][M];
int s[N], ls;
/*
还剩 u 位数要填, 上一次填的是 pre
如果目前走的都是右分支, limit 为真,否则为假
如果目前填的全是 0, lead 为真,否则为假
*/
int calc(int u, int pre, int limit, int lead)
{
if(!u) return 1; // 是合法的 Windy 数, 算 1 个
if(!limit && !lead && f[u][pre] != -1) return f[u][pre]; //记忆化搜索,搜到过直接返回
int res = 0;
int up = s[u];
if(!limit) up = 9; // 没有限制,就可以取 0 ~ 9
for(int i = 0;i <= up;i ++)
{
if(abs(pre - i) < 2) continue; // 如果不合法,直接跳过
if(!i && lead) // 如果还是前导零
{
res += calc(u - 1, -2, limit && (i == up), 1);
}
else
{
res += calc(u - 1, i, limit && (i == up), 0);
}
}
if(!limit && !lead) f[u][pre] = res; // 如果全部算完了,才记忆 f[u][pre]
return res;
}
int dp(int x)
{
ls = 0;
while(x) s[++ ls] = x % 10, x /= 10;
memset(f, -1, sizeof f);
return calc(ls, -2, 1, 1);
}
int main()
{
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}