题目链接Miku

数论dp的典型例题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int dp[1001][15];

//事实上，对于此dp还有个限制
//没有任何限制条件 
int l[1001];
int c;
int p;
int p2;

long long dfs(int pos,int pre,int leadz,int li){
    //当前位置，前一位置，有无前道零，有无限制 
    int ret=0;
    if(pos>p2)
    return 1;
    if(dp[pos][pre]!=-1&&leadz==0&&li==0){
        return dp[pos][pre];
    }
    int lim=li?  l[p2-pos+1] :9;
    //能枚举到那个数由限制决定 
    for(int i=0;i<=lim;++i){
        if(i==0&&leadz) ret+=dfs(pos+1,i,1,i==lim&&li);
        else
        if(i&&leadz) ret+=dfs(pos+1,i,0,i==lim&&li);
        else
        if(abs(pre-i)>=2)
        ret+=dfs(pos+1,i,0,i==lim&&li);
    }
    if(leadz==0&&li==0)
    dp[pos][pre]=ret;
    return ret;
}
long long solve(int p){
    p2=0;
    while(p>0){
        l[++p2]=p%10;
        p/=10; 
    }
    memset(dp,-1,sizeof(dp));
    return dfs(1,0,1,1);
}
int main(){
    cin>>p>>c;
    cout<<solve(c)-solve(p-1);
    return 0;
}