第一道数位DP，花了我四个多小时，好烦人，注释都写满了，解析都免了，中文题目，题意也不用说了，
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; int n,m; int dp[10][3];//dp[i][j],前i位数的状态， /* dp[i][0],表示前i位数且不含不吉利数的个数 dp[i][1],表示前i位数开头放了2的数的个数 dp[i][2],表示前i位数含不吉利数的个数 */ int num[12]; void init() { memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=6;i++) { dp[i][0] = dp[i-1][0] * 9 - dp[i-1][1];//构造一下前i位不含不吉利数个数，因为最后以为可能取6，与下一步的开头取2凑成了不吉利数，所以减去 dp[i][1] = dp[i-1][0];//开头为2的前i位数 就是不含不吉利数前i-1数 dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] * 10;//含有的话一个是本身就含有，那么到了i位就是i-1位乘10，还有前i-1位数不含有因为多了一个4而产生了，最后就是开头为2，因为6而产生了 } } void clear() { memset(num,0,sizeof(num)); } int cal(int x) { clear(); int cnt = 1; int tmpx = x; while(tmpx) { num[cnt++] = tmpx%10; tmpx /= 10; } num[cnt] = 0; bool flag = false; int ans = 0; for(int i=cnt;i>=1;i--) { ans += dp[i-1][2] * num[i]; if(flag)//已经为不吉利 ans += dp[i-1][0] * num[i]; if(!flag && num[i] > 4)//此位大于4，后面可有4 ans += dp[i-1][0]; if(!flag && num[i+1] == 6 && num[i] > 2)//后一位是6，此位大于2 ans += dp[i][1]; if(!flag && num[i] > 6)//此位大于6 ans += dp[i-1][1]; if((num[i] == 2 && num[i+1] == 6) || num[i] == 4) //导致不吉利 flag = true; } return x - ans; } int main() { init(); while(scanf("%d %d",&n,&m), n + m) { clear(); int ans = cal(m+1) - cal(n); printf("%d\n",ans); } return EXIT_SUCCESS; }