AcWing 1083. Windy数
原题链接
中等
作者:
炽热的
,
2023-03-14 23:11:03
,
所有人可见
,
阅读 231
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int len;
int nums[N], f[N][N];
// 只在没有前导 0 的层数记忆化,否则 f[pos][-2] = res.
int dfs(int pos, int pre, int lead, int limit) {
if (!pos) return 1;
if (!limit && !lead && ~f[pos][pre]) return f[pos][pre];
int up = limit ? nums[pos] : 9, res = 0;
for (int i = 0; i <= up; i ++ )
if (max(pre, i) - min(pre, i) >= 2) {
if (lead && !i)
res += dfs(pos - 1, -2, lead && !i, limit && i == up);
else
res += dfs(pos - 1, i, lead && !i, limit && i == up);
}
return limit ? res : (lead ? res : f[pos][pre] = res);
}
int calc(int x) {
len = 0;
memset(f, -1, sizeof f);
while (x) nums[ ++ len] = x % 10, x /= 10;
return dfs(len, -2, 1, 1);
}
int main() {
int l, r;
cin >> l >> r;
cout << calc(r) - calc(l - 1);
return 0;
}