HDU 3555

数位DP
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define LL __int64
 7 using namespace std;
 8 
 9 LL dp[30][3];
10 LL a[30];
11 LL n;
12 void initial(){
13     memset(dp,0,sizeof(dp));
14     dp[0][0]=1LL;
15     for(int i=1;i<30;i++){
16         dp[i][0]=dp[i-1][0]*(LL)10-dp[i-1][1];
17         dp[i][1]=dp[i-1][0];
18         dp[i][2]=dp[i-1][2]*(LL)10+dp[i-1][1];
19     }
20 }
21 
22 LL slove(){
23     LL tmp=n;
24     int len=0;
25     LL ans=0;
26     while(tmp){
27         a[++len]=tmp%(LL)10;
28         tmp/=(LL)10;
29     }
30     a[len+1]=(LL)0;
31     bool flag=false;
32     for(int i=len;i>0;i--){
33         ans+=a[i]*dp[i-1][2];
34         if(flag){
35             ans+=dp[i-1][0]*a[i];
36         }
37         if(!flag&&a[i]>4){
38             ans+=(dp[i-1][1]);
39         }
40         if(a[i+1]==4&&a[i]==9)
41         flag=true;
42     }
43     return ans;
44 }
45 
46 int main(){
47     int T;
48     initial();
49     scanf("%d",&T);
50     while(T--){
51         scanf("%I64d",&n);
52         n++;
53         printf("%I64d
",slove());
54     }
55     return 0;
56 }
View Code