题目地址：
http://acm.hdu.edu.cn/showproblem.php?pid=3555
题目概述：
给出一个数字n，求出1~n中所有含“49”的数字的个数，如1491含有“49”，而4191不含“49”。
大致思路：
初学数位DP，之前做了一个稍微简单的，也是看了某dalao的blog才明白一点点，这里附上dalao的blog地址：http://blog.csdn.net/wubaizhe/article/details/54706356
题目要求含“49”的数的个数，实际上求出不含“49”的数的个数也是可以的，注意要开long long。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <vector> 6 #include <ctime> 7 #include <map> 8 #include <stack> 9 #include <queue> 10 #include <cstring> 11 #include <algorithm> 12 using namespace std; 13 14 #define sacnf scanf 15 #define scnaf scanf 16 #define maxn 25 17 #define maxm 10 18 #define inf 1061109567 19 #define Eps 0.00001 20 const double PI=acos(-1.0); 21 #define mod 1000000007 22 #define MAXNUM 10000 23 void Swap(int &a,int &b) {int t=a;a=b;b=t;} 24 int Abs(int x) {return (x<0)?-x:x;} 25 typedef long long ll; 26 typedef unsigned int uint; 27 28 ll f[maxn][maxm]; 29 int num[maxn]; 30 31 ll calc(ll x) 32 { 33 int cnt=0; 34 while(x) 35 { 36 num[cnt++]=x%10; 37 x/=10; 38 } 39 num[cnt]=0;ll ans=0; 40 for(int i=cnt;i>=1;i--) 41 { 42 for(int j=0;j<num[i-1];j++) 43 { 44 if(j!=9||num[i]!=4) 45 ans+=f[i][j]; 46 } 47 if(num[i-1]==9&&num[i]==4) break; 48 } 49 return ans; 50 } 51 52 int main() 53 { 54 //freopen("data.in","r",stdin); 55 //freopen("data.out","w",stdout); 56 //clock_t st=clock(); 57 for(int i=0;i<10;i++) f[1][i]=1; 58 for(int i=2;i<=21;i++) 59 { 60 for(int j=0;j<10;j++) 61 { 62 for(int k=0;k<10;k++) 63 { 64 if(j!=4||k!=9) 65 f[i][j]+=f[i-1][k]; 66 } 67 } 68 } 69 int T;ll n;scanf("%d",&T); 70 while(T--) 71 { 72 scanf("%lld",&n); 73 ll ans=calc(n+1)-1; 74 printf("%lld ",n-ans); 75 } 76 //clock_t ed=clock(); 77 //printf(" Time Used : %.5lf Ms. ",(double)(ed-st)/CLOCKS_PER_SEC); 78 return 0; 79 }