题目连接：hdu_3555_Bomb
题意：和2089一样，只是数据大了点，不过道理是一样的
1 #include<cstdio> 2 #include<cstring> 3 #define F(i,a,b) for(__int64 i=a;i<=b;i++) 4 5 __int64 t,n,dp[65][10][2],dig[65],len; 6 7 __int64 dfs(int pos,int pre,bool have,bool inf){ 8 if(!pos)return have; 9 if(!inf&&dp[pos][pre][have]!=-1)return dp[pos][pre][have]; 10 long long end=inf?dig[pos]:9,ans=0; 11 F(i,0,end)if(pre==4&&i==9)ans+=dfs(pos-1,i,1,inf&&(i==end)); 12 else ans+=dfs(pos-1,i,have,inf&&(i==end)); 13 if(!inf)dp[pos][pre][have]=ans; 14 return ans; 15 } 16 17 int main(){ 18 memset(dp,-1,sizeof(dp)); 19 scanf("%I64d",&t); 20 while(t--){ 21 scanf("%I64d",&n); 22 for(len=0;n;n/=10)dig[++len]=n%10; 23 printf("%I64d ",dfs((int)len,0,0,1)); 24 } 25 return 0; 26 }