题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3555

题目大意：就是给你一个数n，判断从0到n有多少个数含有数字49.。。。。。

是不是觉得跟hdu2089很相似呀。。。

思路：跟hdu2089一样的，注意给出的数比较大，所以这儿用__int64 。。。。

code：

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; __int64 dp[25][3]; void Init() { memset(dp,0,sizeof(dp)); int i; dp[0][0]=1; for(i=1;i<=20;i++) { dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; } } __int64 solve(__int64 n) { __int64 i,len=0,ans,flag,digit[25]; memset(digit,0,sizeof(digit)); while(n) { digit[++len]=n%10; n/=10; } ans=0; flag=0; for(i=len;i>0;i--) { //printf("%d ",ans); ans+=dp[i-1][2]*digit[i]; if(flag) { ans+=dp[i-1][0]*digit[i]; } if(!flag&&digit[i]>4) { ans+=dp[i-1][1]; } if(digit[i+1]==4&&digit[i]==9) { flag=1; } } return ans; } int main() { Init(); int T; __int64 n; scanf("%d",&T); while(T--) { scanf("%I64d",&n); printf("%I64d\n",solve(n+1)); } return 0; }