數位dp基礎題目

[cpp]
/********************
language:c++  
author:pirates
problem:hdu2089 
style:數位dp 
*********************/ 
 
 
#include<iostream>  
#include<stdio.h>  
#include<algorithm>  
using namespace std; 
#define Maxx 1000010  
int dp[10][10]; 
//dp[i][0] 代表不是不吉利的個數  
//dp[i][1] 代表最高位為2的個數且是非不吉利數   
//dp[i][2] 代表不吉利個數的總數，62或4都不能存在   
void Init() 
{ 
    dp[0][0]=1; 
    for(int i=1;i<=6;i++) 
    { 
        dp[i][0]=dp[i-1][0]*9-dp[i-1][1];//最高位除了4，選擇其它9個數，但在2之前可能存在6，所以要減去第二位2的個數  
        dp[i][1]=dp[i-1][0]; //最高位只有2可以選   
        dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];//  
    } 
} 
int Solve(int n) 
{ 
    int i,j,flag=0; 
    int bit[10]; 
    int len=0; 
    int tem=n; 
    while(n) 
    { 
        bit[++len]=n%10; 
        n/=10; 
    } 
    bit[len+1]=0; 
    int ans=0; 
    for(int i=len;i>=0;i--) 
    { 
        ans+=dp[i-1][2]*bit[i]; //存在不吉利的數的總數   
        if(flag)     
            ans+=dp[i-1][0]*bit[i]; 
        else  
        { 
            if(bit[i]>4) 
                ans+=dp[i-1][0];    //高位可能出現4的情況   
            if(bit[i+1]==6&&bit[i]>2) 
                ans+=dp[i][1];  //高位為6，第二為可能為2的情況   
            if(bit[i]>6) 
                ans+=dp[i-1][1]; 
            if(bit[i]==4 || (bit[i+1]==6&&bit[i]==2)) 
                flag=1; 
        }        
    } 
    return tem-ans; 
}  
int main() 
{ 
    int n,m,i,j; 
    Init(); 
    while(scanf("%d%d",&n,&m)) 
    { 
        if(!n&&!m) break; 
        printf("%d\n",Solve(m+1)-Solve(n));  
    } 
    return 0; 
} 

/********************
language:c++ 
author:pirates
problem:hdu2089
style:數位dp
*********************/

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define Maxx 1000010
int dp[10][10];
//dp[i][0] 代表不是不吉利的個數
//dp[i][1] 代表最高位為2的個數且是非不吉利數
//dp[i][2] 代表不吉利個數的總數，62或4都不能存在
void Init()
{
 dp[0][0]=1;
 for(int i=1;i<=6;i++)
 {
  dp[i][0]=dp[i-1][0]*9-dp[i-1][1];//最高位除了4，選擇其它9個數，但在2之前可能存在6，所以要減去第二位2的個數
  dp[i][1]=dp[i-1][0]; //最高位只有2可以選
  dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];//
 }
}
int Solve(int n)
{
 int i,j,flag=0;
 int bit[10];
 int len=0;
 int tem=n;
 while(n)
 {
  bit[++len]=n%10;
  n/=10;
 }
 bit[len+1]=0;
 int ans=0;
 for(int i=len;i>=0;i--)
 {
  ans+=dp[i-1][2]*bit[i]; //存在不吉利的數的總數
  if(flag) 
   ans+=dp[i-1][0]*bit[i];
  else
  {
   if(bit[i]>4)
    ans+=dp[i-1][0];  //高位可能出現4的情況
    if(bit[i+1]==6&&bit[i]>2)
     ans+=dp[i][1]; //高位為6，第二為可能為2的情況
    if(bit[i]>6)
     ans+=dp[i-1][1];
    if(bit[i]==4 || (bit[i+1]==6&&bit[i]==2))
    flag=1;
  }  
 }
 return tem-ans;
}
int main()
{
 int n,m,i,j;
 Init();
 while(scanf("%d%d",&n,&m))
 {
  if(!n&&!m) break;
  printf("%d\n",Solve(m+1)-Solve(n)); 
 }
 return 0;
}[cpp]
/********************
language:c++  
author:pirates
problem:hdu3555
style:數位dp 
*********************/ 
 
 
#include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std; 
 
//dp[i][0] 代表不出現49的個數  
//dp[i][1] 最高位為9的個數  
//dp[i][2] 出現49的 個數   
typedef __int64 ll; 
ll dp[30][3]; 
void Init() 
{ 
    ll i; 
    memset(dp,0,sizeof(dp));  
    dp[0][0]=1;  
    for(i=1;i<=30;i++){ 
        dp[i][0]=(ll)dp[i-1][0]*10-dp[i-1][1]; //不出現49的個數     
        dp[i][1]=(ll)dp[i-1][0];    //最高位為9的個數  
        dp[i][2]=(ll)dp[i-1][2]*10+dp[i-1][1]; //出現49的個數   
    }  
}  
ll Solve(ll n) 
{ 
    ll i,j,len=0; 
    ll bit[25];  
    while(n) 
    { 
        bit[++len]=n%10; 
        n/=10; 
    } 
    bit[len+1]=0; 
    ll ans=0; 
    ll flag=0; 
    for(i=len;i>0;i--) 
    { 
        ans+=(ll)dp[i-1][2]*bit[i]; 
        if(flag) 
            ans+=(ll)dp[i-1][0]*bit[i];  
        else 
        { 
            if(bit[i]>4) 
                ans+=dp[i-1][1]; 
            if(bit[i+1]==4 && bit[i]==9) 
                flag=1; 
        }        
    } 
    return ans; 
} 
 
int main() 
{ 
    Init(); 
    ll n,m,T; 
    scanf("%I64d",&T); 
    while(T--) 
    { 
        scanf("%I64d",&n); 
        printf("%I64d\n",Solve(n+1)); 
    } 
    return 0; 
} 

/********************
language:c++ 
author:pirates
problem:hdu3555
style:數位dp
*********************/

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

//dp[i][0] 代表不出現49的個數
//dp[i][1] 最高位為9的個數
//dp[i][2] 出現49的 個數
typedef __int64 ll;
ll dp[30][3];
void Init()
{
 ll i;
 memset(dp,0,sizeof(dp));
 dp[0][0]=1;
 for(i=1;i<=30;i++){
  dp[i][0]=(ll)dp[i-1][0]*10-dp[i-1][1]; //不出現49的個數  
  dp[i][1]=(ll)dp[i-1][0]; //最高位為9的個數
  dp[i][2]=(ll)dp[i-1][2]*10+dp[i-1][1]; //出現49的個數
 }
}
ll Solve(ll n)
{
 ll i,j,len=0;
 ll bit[25];
 while(n)
 {
  bit[++len]=n%10;
  n/=10;
 }
 bit[len+1]=0;
 ll ans=0;
 ll flag=0;
 for(i=len;i>0;i--)
 {
  ans+=(ll)dp[i-1][2]*bit[i];
  if(flag)
   ans+=(ll)dp[i-1][0]*bit[i];
  else
  {
   if(bit[i]>4)
    ans+=dp[i-1][1];
   if(bit[i+1]==4 && bit[i]==9)
    flag=1;
  }  
 }
 return ans;
}

int main()
{
 Init();
 ll n,m,T;
 scanf("%I64d",&T);
 while(T--)
 {
  scanf("%I64d",&n);
  printf("%I64d\n",Solve(n+1));
 }
 return 0;
}
[cpp
/***************
language:c++  
author:pirates
problem:相鄰兩數差2 
style:數位dp
****************/  
 
#include<iostream>  
#include<stdio.h>  
#include<algorithm>  
#include<string.h>  
using namespace std; 
int dp[15][10]; 
void Init() 
{    
    int i,j,k; 
    memset(dp,0,sizeof(dp)); 
    for(i=0;i<10;i++) 
        dp[1][i]=1; 
    for(i=2;i<=10;i++) 
        for(j=0;j<10;j++) 
            for(k=0;k<10;k++) 
                if(abs(j-k)>=2) 
                    dp[i][j]+=dp[i-1][k];   
} 
int Solve(int n) 
{ 
    int len=0,i,j,bit[15]; 
    while(n) 
    { 
        bit[++len]=n%10; 
        n/=10; 
    } 
    bit[len+1]=0; 
    int ans=0; 
    for(i=1;i<len;i++)   //統計每位的情況   
        for(j=1;j<bit[i];j++) 
            ans+=dp[i][j]; 
    for(i=1;i<bit[len];i++)  //最高位的情況   
        ans+=dp[len][i];     
    for(i=len-1;i;i--)      //  
        for(j=0;j<bit[i];j++){ 
            if(abs(j-bit[i+1])>=2) 
            ans+=dp[i][j]; 
        if(abs(bit[i+1]-bit[i])<2) break; 
    } 
    return ans; 
} 
int main() 
{ 
    Init(); 
    int i,j,n,m; 
    scanf("%d%d",&n,&m); 
    printf("%d\n",Solve(m+1)-Solve(n));  
    return 0; 
}