题目描述
https://www.luogu.com.cn/problem/P2657
Solution
我们令d[pos][pre]表示上一位是pre，从个位到第pos位
然后套数位dp的板子即可
时间复杂度应该是 $O(len^3)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 11
#define ll long long
using namespace std;
int a, b;
int f[maxn][maxn], d[maxn], len;
int dfs(int pos, bool limit, bool lead, int pre) {
if (!pos) return 1;
if (!limit && !lead && ~f[pos][pre]) return f[pos][pre];
int up = limit ? d[pos] : 9; ll sum = 0;
for (int i = 0; i <= up; ++i) {
if (abs(i - pre) < 2 && !lead) continue;
sum += dfs(pos - 1, limit && i == d[pos], lead && !i, i);
}
if (!limit && !lead) f[pos][pre] = sum;
return sum;
}
int solve(int x) { len = 0;
while (x) {
d[++len] = x % 10;
x /= 10;
}
return dfs(len, 1, 1, 0);
}
int main() {
cin >> a >> b; memset(f, -1, sizeof f);
cout << solve(b) - solve(a - 1) << endl;
return 0;
}
|