学步园

中文题

思路：数位DP，dp[i][j]表示到第i位，最后一位为j的情况，然后根据数位DP进行转移即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 12;
int n, m, d[N], dn, dp[N][N];

void get(int x) {
	if (x == 0) {
		dn = 1;
		d[dn] = 0;
		return;
	}
	dn = 0;
	while (x) {
		d[++dn] = x % 10;
		x /= 10;
 	}
 	for (int i = 1; i <= dn / 2; i++)
 		swap(d[i], d[dn - i + 1]);
}

int solve(int x) {
	get(x);
	int pre = 11, flag = 0;
	dp[0][11] = 1;
	for (int i = 1; i <= dn; i++) {
		for (int j = 0; j <= 9; j++) {
			dp[i][j] = 0;
			if (j == 4) continue;
			for (int k = 0; k <= 9; k++) {
				if (k == 4 || (k == 6 && j == 2)) continue;
				dp[i][j] += dp[i - 1][k];
   			}
  		}
		if (flag) continue;
  		for (int j = 0; j < d[i]; j++) {
  			if (j == 4 || (pre == 6 && j == 2)) continue;
  			dp[i][j]++;	
  		}
  		if (d[i] == 4 || (pre == 6 && d[i] == 2)) flag = 1;	
  		pre = d[i];
 	}
 	int ans = 0;
 	for (int i = 0; i <= 9; i++)
 		ans += dp[dn][i];
	if (!flag) ans++;
	return ans;
}

int main() {	
	while (~scanf("%d%d", &n, &m) && n || m) {
		printf("%d\n", solve(m) - solve(n - 1));
	}	
	return 0;
}