HDU - 2089 不要62

题目链接

---

大致题意:

总结来说,给一个区间，统计区间中不含4和62的数字个数

---

解题思路:

数位dp模板题

对于62的情况我们需要记录上一位数字,所以用到pre

定义状态方程: f[i][2] 表示到第i位,且上一位是不是6的数字个数

在搜索枚举每一位数字时,当遇到4或者连续62直接跳过,那么只要枚举到最低位的数字一定是符合条件的,记录答案

---

AC代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N = 10;int a[N];
ll f[N][2];ll dfs(int len, int limit, int pre) {if (!len)return 1;if (!limit && f[len][pre] != -1)return f[len][pre];ll res = 0;int end = limit ? a[len] : 9;for (int i = 0; i <= end; ++i) {if (i == 4 || pre && i == 2)continue;res += dfs(len - 1, limit && i == end, i == 6);}if (!limit)f[len][pre] = res;return res;
}
ll dp(ll n) {memset(f, -1, sizeof f);int len = 0;while (n)a[++len] = n % 10, n /= 10;return dfs(len, 0, 1);
}
int main()
{ll l, r;while (cin >> l >> r, l + r) {cout << dp(r) - dp(l - 1) << endl;}return 0;
}