http://acm.hdu.edu.cn/showproblem.php?pid=3555
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll __int64 5 using namespace std; 6 7 ll dp[30][3]; 8 int num[30]; 9 10 void inti() 11 { 12 memset(dp,0,sizeof(dp)); 13 dp[0][0]=1; 14 dp[0][1]=0; 15 dp[0][2]=0; 16 for(int i=1; i<30; i++) 17 { 18 dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; 19 dp[i][1]=dp[i-1][0]; 20 dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; 21 } 22 } 23 24 int main() 25 { 26 int t; 27 scanf("%d",&t); 28 inti(); 29 while(t--) 30 { 31 ll n; 32 scanf("%I64d",&n); 33 int cnt=0; 34 while(n) 35 { 36 num[++cnt]=n%10; 37 n=n/10; 38 } 39 num[cnt+1]=0; 40 bool flag=false; 41 ll ans=0; 42 for(int i=cnt; i>=1; i--) 43 { 44 ans+=dp[i-1][2]*num[i]; 45 if(flag) ans+=dp[i-1][0]*num[i]; 46 else if(!flag&&num[i]>4) 47 { 48 ans+=dp[i-1][1]; 49 } 50 if(num[i+1]==4&&num[i]==9) 51 { 52 flag=true; 53 } 54 } 55 if(flag) ans++; 56 printf("%I64d ",ans); 57 } 58 return 0; 59 }