枚举、预处理,len-1位,len位但小于第一个数的这些都不讲了,看这篇题解 windy
讲一下贴近最高位的处理。
因为最高位如果取了,后面位数只能取到最高位,而不是9,而后面的数也是同理,所以我们的内部 $ \ j \ $ 循环枚举范围要把\(num_i\)单独拿出来判,单独拿出来的原因是好判break一些,因为已经不合法了,后面也必然不可能产生贡献了。
#include<bits/stdc++.h>
using namespace std;
int a,b;
long long ans;
int dp[15][11];
int numa[15],numb[15],l,r;
int main(){
for(int i=0;i<=9;++i) dp[1][i]=1;
for(int i=1;i<=11;++i){
for(int j=0;j<=9;++j){
for(int k=0;k<=9;++k)
if(abs(j-k)>=2) dp[i][j]+=dp[i-1][k];
}
}
scanf("%d %d",&a,&b);
++b;
while(a) numa[++l]=a%10,a/=10;
while(b) numb[++r]=b%10,b/=10;
for(int i=1;i<=l-1;++i){
for(int j=1;j<=9;++j) ans-=dp[i][j];
}
for(int i=1;i<numa[l];++i) ans-=dp[l][i];
for(int i=l-1;i>0;--i){
for(int j=0;j<=numa[i]-1;++j){
if(abs(j-numa[i+1])>=2) ans-=dp[i][j];
}
if(abs(numa[i]-numa[i+1])<2) break;
}
for(int i=1;i<=r-1;++i){
for(int j=1;j<=9;++j) ans+=dp[i][j];
}
for(int i=1;i<numb[r];++i) ans+=dp[r][i];
for(int i=r-1;i>0;--i){
for(int j=0;j<=numb[i]-1;++j){
if(abs(j-numb[i+1])>=2) ans+=dp[i][j];
}
if(abs(numb[i]-numb[i+1])<2) break;
}
printf("%lld",ans);
}
标签:10,int,题解,windy,numa,numb,P2657,dp
From: https://www.cnblogs.com/mountzhu/p/18415719