用一个dp数组，储存不同长度下的每种状态。
#include <cstdio> #include <iostream> #include <cstring> using namespace std; //表示长度为len的数字的三种状态 //0~没有不吉利数并且末尾不为6，1~没有不吉利数末尾是6, 2~含有不吉利的个数 int dp[10][3]; int DP(int x) { bool flag = false; int s[15]; int p = 0,sum = x,ans = 0; while (x) { s[++p] = (x%10); x /= 10;} s[p + 1] = 0; for(int i = p; i > 0; i--) { //由上位所有不吉利数推导 ans += (dp[i - 1][2]*s[i]); //之前出现不吉利的数字 if(flag) ans += (dp[i - 1][0]*s[i]); else { if(s[i] > 4) ans += dp[i - 1][0];//出现4 if(s[i] > 6) ans += dp[i - 1][1];//出现6 if(s[i + 1] == 6 && s[i] > 2) ans += dp[i][1];//出现62 } if(s[i] == 4 || s[i + 1] == 6 && s[i] == 2) flag = true; } //所有的数减去不吉利的数 return sum - ans; } int main() { int a, b; memset(dp, 0, sizeof(dp)); //预处理dp dp[0][0] = 1; for(int i = 1; i <= 8; i++) { //在不含不吉利数的末位分别补除了4的9个数字，减去在6后面补2的个数 dp[i][0] = dp[i-1][0]*9 - dp[i-1][1]; //在不含不吉利数在末位补6 dp[i][1] = dp[i-1][0]; //各种出现不吉利数的情况，上一次出现（不吉利的*10+含有6+含有4） dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0]; } while (scanf("%d%d",&a,&b) != EOF) { if(a + b == 0) break; printf("%d ", DP(b + 1) - DP(a)); } return 0; }