bzoj 1026--windy数 简单数位DP

#include<cstdio>
#include<cstdlib>
using namespace std;

long long dp[20][10];

void init(){
  
  for(int i=0;i<10;i++) dp[1][i]=1;
  for(int i=2;i<=10;i++){
    for(int j=0;j<10;j++){
      for(int k=0;k<10;k++){
        if(abs(j-k)>=2) dp[i][j]+=dp[i-1][k];
      }
    }
  }
}

long long getnum(int x){
  
  int d[20];
  int len=0;
  if(!x) return 0;
  while(x){
    
    d[len++]=x%10;
    x/=10; 
  }
  long long ans=0;
  for(int i=1;i<len;i++){
    for(int j=1;j<10;j++) ans+=dp[i][j];
  }
  for(int j=1;j<d[len-1];j++) ans+=dp[len][j];
  len--;
  while(len>=1){
    if(len==1) d[0]++;
    for(int i=0;i<d[len-1];i++){
      
      if(abs(i-d[len])>=2) ans+=dp[len][i];
    }
    if(abs(d[len-1]-d[len])<2) break;
    len--;
  }
  return ans;
}

int main(){
  
  int a,b;
  scanf("%d%d",&a,&b);
  init();
  printf("%d\n",getnum(b)-getnum(a-1));
}