直接数位DP不解释
好吧……记录一下相邻的差，然后搞一搞
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const long long N=15;
long long A,B,dp[N][10],a[N];
long long Abs(long long x){return x>0?x:-x;}
void Pre(){
memset(dp,0,sizeof(dp));
for(long long i=0;i<=9;i++)dp[1][i]=1;
for(long long i=2;i<=10;i++){
for(long long j=0;j<=9;j++){
for(long long k=0;k<=9;k++)if(Abs(j-k)>=2)dp[i][j]+=dp[i-1][k];
}
}
}
long long DP(long long x){
if(x==0)return 0;
long long cnt=0,ans=0;
while(x){a[++cnt]=x%10;x/=10;}
for(long long i=1;i<=cnt/2;i++)swap(a[i],a[cnt-i+1]);
for(long long i=1;i<a[1];i++)ans+=dp[cnt][i];
for(long long i=1;i<cnt;i++){
for(long long j=1;j<=9;j++)ans+=dp[i][j];
}
for(long long i=2;i<=cnt;i++){
for(long long j=0;j<a[i];j++)if(Abs(j-a[i-1])>=2)ans+=dp[cnt-i+1][j];
if(Abs(a[i]-a[i-1])<2)break;
}
return ans;
}
int main(){
freopen("1026.in","r",stdin);
freopen("1026.out","w",stdout);
scanf("%lld %lld",&A,&B);
Pre();
printf("%lld\n",DP(B+1)-DP(A));
return 0;
}
评论 (0)
