数位dp基础题目 (二)

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

#include
#include
#include
#include
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
#include
#include
#include
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 for(j=1;j ans+=dp[i][j];
for(i=1;i ans+=dp[len][i];
for(i=len-1;i;i--) //
for(j=0;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;
}