HDOJ - 3555 按位DP..

      方法很簡單..統計起來比較蛋疼... WA得想吐..參考了別人的代碼才過的 ...

    特別注意的是當前數字前面幾位已經有49出現的情況....

Program:

[cpp]
#include<iostream>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<set>  
#include<algorithm>  
#include<stdio.h>  
#include<string.h>  
#define ll unsigned long long  
#define oo 1000000007  
using namespace std;  
ll dp[23][3]; 
void pre() 
{ 
       int i,j,k; 
       memset(dp,0,sizeof(dp)); 
       dp[0][0]=1;  
       for (i=1;i<=22;i++) 
       { 
              dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//長度為i的數最且不含49的個數  
              dp[i][1]=dp[i-1][0];//長度為i的數最高位為9且不含49的個數   
              dp[i][2]=10*dp[i-1][2]+dp[i-1][1];// 長度為i的數包含的49個數   
       } 
       return; 
} 
ll getans(ll n) 
{ 
       ll p,ans,l,s[22];  
       bool f=false; 
       l=0; 
       s[0]=0; 
       while (n) 
       { 
             s[++l]=n%10; 
             n/=10; 
       } 
       ans=0;           
       for(p=l;p>=1;p--) 
       { 
            ans+=dp[p-1][2]*s[p]; 
            if(f) 
                ans+=dp[p-1][0]*s[p]; 
            else 
                if(s[p]>4) ans+=dp[p-1][1]; 
            if(s[p+1]==4 && s[p]==9) f=true; 
       }  
       return ans; 
} 
int main() 
{          
       int T; 
       ll n; 
       scanf("%d",&T); 
       pre(); 
       while (T--) 
       { 
             cin>>n; 
             n++; 
             cout<<getans(n)<<endl; 
       } 
       return 0; 
} 

#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
#include<set>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#define ll unsigned long long
#define oo 1000000007
using namespace std;
ll dp[23][3];
void pre()
{
       int i,j,k;
       memset(dp,0,sizeof(dp));
       dp[0][0]=1;
       for (i=1;i<=22;i++)
       {
              dp[i][0]=dp[i-1][0]*10-dp[i-1][1];//長度為i的數最且不含49的個數
              dp[i][1]=dp[i-1][0];//長度為i的數最高位為9且不含49的個數
              dp[i][2]=10*dp[i-1][2]+dp[i-1][1];// 長度為i的數包含的49個數
       }
       return;
}
ll getans(ll n)
{
       ll p,ans,l,s[22];
       bool f=false;
       l=0;
       s[0]=0;
       while (n)
       {
             s[++l]=n%10;
             n/=10;
       }
       ans=0;         
       for(p=l;p>=1;p--)
       {
            ans+=dp[p-1][2]*s[p];
            if(f)
                ans+=dp[p-1][0]*s[p];
            else
                if(s[p]>4) ans+=dp[p-1][1];
            if(s[p+1]==4 && s[p]==9) f=true;
       }
       return ans;
}
int main()
{        
       int T;
       ll n;
       scanf("%d",&T);
       pre();
       while (T--)
       {
             cin>>n;
             n++;
             cout<<getans(n)<<endl;
       }
       return 0;
}