首先，这显然是一道比较简单数位dp题，不会的可以去看一下这篇教程。
这题和版子题一样，只不过条件变了一些，直接记忆化搜索即可。
附上代码(详见注释)。
#include<bits/stdc++.h>
using namespace std;
const int N=15;
// dp 数组用于记忆化搜索，dp[pos][last] 表示当前处理到第 pos 位，上一位数字是 last 时的合法方案数
int dp[N][N];
int num[N];
// dfs 函数用于深度优先搜索
// pos 表示当前处理到数字的第几位
// last 表示上一位数字
// lead 表示是否有前导零
// limit 表示当前位是否受到数字上限的限制
int dfs(int pos,int last,bool lead,bool limit)
{
int ans=0;
// 如果已经处理完所有位，说明找到了一个合法方案，返回 1
if(pos==0)return 1;
// 如果没有前导零且没有上限限制，并且该状态已经计算过，则直接返回结果
if(!lead&&!limit&&dp[pos][last]!=-1)return dp[pos][last];
// 确定当前位的上限，如果有限制则为 num[pos]，否则为 9
int up=(limit?num[pos]:9);
// 枚举当前位可以取的数字
for(int i=0;i<=up;i++){
// 如果当前数字与上一位数字的差的绝对值小于 2，则跳过
if(abs(i-last)<2)continue;
// 如果有前导零且当前数字为 0
if(lead&&i==0)
// 继续搜索下一位，保持前导零状态，更新上限限制
ans+=dfs(pos-1,-2,true,limit&&i==up);
else
// 没有前导零，更新上一位数字，更新前导零状态，更新上限限制
ans+=dfs(pos-1,i,false,limit&&i==up);
}
// 如果没有上限限制且没有前导零，将当前状态的结果存入 dp 数组
if(!limit&&!lead)
dp[pos][last]=ans;
return ans;
}
// slove 函数用于处理一个整数 x，计算小于等于 x 的满足条件的数字个数
int slove(int x)
{
int len=0;
// 将数字 x 的每一位存入 num 数组
while(x){
num[++len]=x%10;
x/=10;
}
// 初始化 dp 数组为 -1，表示未计算过
memset(dp,-1,sizeof(dp));
// 从最高位开始搜索
return dfs(len,-2,true,true);
}
signed main()
{
int a,b;
cin>>a>>b;
// 计算区间 [a, b] 内满足条件的数字个数
cout<<slove(b)-slove(a-1);
return 0;
}
健康查询