题解：P13085 [SCOI2009] windy 数（加强版）

· · 题解

显然，这是一道数位 dp。这不是废话吗。如果不知道什么是数位 dp，请移步至P2602 [ZJOI2010] 数字计数，那里有超详细的讲解。

其实所有的数位 dp 都一个套路，只是改一下要求。只需要注意一下两数之差为绝对值，不要忘记前导零，再稍微注意一下细节，就可愉快的通过本题了。

思路概述：先将原数按位拆解，在从高位到低位挨个枚举，同时进行记忆化保证时间复杂度。

解释一下：last 之所以要初始化为-2，是为了保证首位可以填0。

代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int dp[20][20][2][2],num[20];
int dfs(int pos,int last,bool flag,bool lead){
    /*
    lead表示是否有前导零，flag表示是否受限制 
    */
    if(pos==0)return 1;//若pos==0，则表示找到一个可行的数 
    if(dp[pos][last][flag][lead]!=-1)return dp[pos][last][flag][lead];//记忆化优化 
    int ans=0,up=9;
    if(flag)up=num[pos];//up为当前数位可取的最大值 
    for(int i=0;i<=up;i++){
        if(abs(i-last)>=2||lead)ans+=dfs(pos-1,i,flag&&(i==up),lead&&(i==0));
    }
    dp[pos][last][flag][lead]=ans;
    return ans;
}
int work(int x){//预处理  
    memset(dp,-1,sizeof(dp));
    int len=0;
    while(x){
        num[++len]=x%10;
        x/=10;
    }
    return dfs(len,-2,1,1);
}
int a,b;
signed main(){
    scanf("%lld%lld",&a,&b);
    printf("%lld",work(b)-work(a-1));//因为 a 这个数也要被判断，所以是 work(a-1) 
    return 0;
}

~最后，不开long long见祖宗。~