数位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=

补充：软件开发 , C++ ,