1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int L, R; int dp[15][10]; // 记忆化搜索 dp[pos][pre] int d[15], dlen; // d[dlen]~d[1] // 做到了第 pos 位,前一位是 pre,是否顶到了上限,之前是否都填的 0 int dfs(int pos, int pre, bool limit, bool zero) { if (pos == 0) return 1; // 算过了没贴边的结果的话就直接返回 if (!limit && !zero && dp[pos][pre] != -1) return dp[pos][pre]; // 当前这一位的上限 int up = limit ? d[pos] : 9; int sum = 0; // 记录方案数 for (int now = 0; now <= up; now++) // 枚举当前这一位 { if (zero) // 当前是第一个数,前面都是前导 0 { // 第一个数没有差至少为2的限制 sum += dfs(pos - 1, now, limit && now == d[pos], zero && now == 0); } else { if (abs(now - pre) < 2) continue; sum += dfs(pos - 1, now, limit && now == d[pos], zero && now == 0); } } // 如果前面没贴边,就记忆化一下 if (!limit && !zero) dp[pos][pre] = sum; return sum; } int cal(int x) { if (x == 0) return 1; dlen = 0; for (int i = x; i != 0; i /= 10) d[++dlen] = i % 10; return dfs(dlen, 0, true, true); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> L >> R; memset(dp, -1, sizeof(dp)); cout << cal(R) - cal(L - 1) << "\n"; return 0; }
- 1
信息
- ID
- 817
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 56
- 已通过
- 23
- 上传者