题目链接：点击打开链接
中文题。
问区间内有多少个合法数字（一个数是合法数字须满足1、不含4 ，2、每个6后面都不是2
dp[i][0]表示长度为i的数字中，，前一位不为6时的合法个数， dp[i][1]表示长度为i的数字中前一位是6的合法个数。
#include <cstdio>#include <algorithm>#include <cstring>#include <iostream>using namespace std;typedef long long ll;const int N = 50;int bit[N];int dp[N][2];int dfs(int len, int presix, bool flag){if (len == 0)return 1;if (!flag && dp[len][presix] != -1)return dp[len][presix];int ans = 0;int end = flag ? bit[len] : 9;for (int i = 0; i <= end; i++){if (i == 4 || (presix && i==2))continue;ans += dfs(len – 1, i == 6, flag&&i == end);}if (!flag)dp[len][presix] = ans;return ans;}int solve(int x){if (x <= 0)return 1;int len = 0;for (int tmp = x; tmp; tmp /= 10)bit[++len] = tmp % 10;return dfs(len, 0, true);}int main() {int l, r;memset(dp, -1, sizeof dp);while (cin >> l >> r, l+r)cout << solve(r) – solve(l – 1) << endl;return 0;}
思想如钻子，必须集中在一点钻下去才有力量
