hdu3555 數位dp入門題

hdu3555

給出T個N，對每一個N求1~N中有多少個數含49   (如 49,449,12349,2491等)

[cpp]
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<cmath>  
using namespace std; 
 
__int64 N,dp[33][3],sum; 
int bit[33]; 
 
int main() 
{ 
    int i,j,T,len; 
    memset(dp,0,sizeof(dp));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][1]+dp[i-1][2]*10; 
    } 
    scanf("%d",&T); 
    while(T--){ 
        scanf("%I64d",&N); 
        N++;  
        len=sum=0; 
        while(N){ 
            bit[++len]=N%10; 
            N/=10; 
        } 
        bit[len+1]=0; 
        bool flag=0; 
        for(i=len;i>=1;i--){ 
            sum+=dp[i-1][2]*bit[i]; 
            if(!flag&&bit[i]>4)  sum+=dp[i-1][1];     
            if(flag)    sum+=dp[i-1][0]*bit[i]; 
            if(bit[i+1]==4&&bit[i]==9)  flag=1; 
        } 
        cout<<sum<<endl; 
    } 
    return 0; 
} 
 
/*
 
*/ 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

__int64 N,dp[33][3],sum;
int bit[33];

int main()
{
 int i,j,T,len;
 memset(dp,0,sizeof(dp));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][1]+dp[i-1][2]*10;
 }
 scanf("%d",&T);
 while(T--){
  scanf("%I64d",&N);
  N++;
  len=sum=0;
  while(N){
   bit[++len]=N%10;
   N/=10;
  }
  bit[len+1]=0;
  bool flag=0;
  for(i=len;i>=1;i--){
   sum+=dp[i-1][2]*bit[i];
   if(!flag&&bit[i]>4) sum+=dp[i-1][1]; 
   if(flag) sum+=dp[i-1][0]*bit[i];
   if(bit[i+1]==4&&bit[i]==9) flag=1;
        }
  cout<<sum<<endl;
 }
 return 0;
}

/*

*/