HYSBZ - 1026 windy数 [数位DP]

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？

　　包含两个整数，A B。

　　一个整数

 1 #include 2 using namespace std;
 3 #include 4 #include 5 #include 6 typedef long long ll;
 7 ll a,b;
 8 ll f[100][13];
 9 int number[100];
10 ll dfs(int bit,int pre,int limit,int zero){
11     if(bit==-1){
12         return 1;}
13     if(limit==0&&f[bit][pre]!=-1LL&&zero==0)
14         return f[bit][pre];
15     int up = limit?number[bit]:9;
16     int ans = 0;
17     for(int i=0;i){
18          int d = pre - i;//位数之间的差 
19          if(d0)//取绝对值 
20              d*=-1;
21          if(zero==0&&d2)//排除不符合题意的情况 
22              continue;
23          ans = ans + dfs(bit-1,i,limit&&i==number[bit],zero&&i==0);
24     }
25     if(!limit&&!zero)
26         f[bit][pre] = ans;
27     return ans;
28 }
29 ll get(ll x){
30     int num = 0;
31     memset(number,0,sizeof(number));
32     ll pt = x;
33     while(pt>0LL){
34         number[num++]=pt%10;
35         pt/=10LL;
36     }
37     num-=1;
38     memset(f,-1,sizeof(f));
39     ll ans = dfs(num,12,1,1);
40     return ans;
41 }
42 int main(){
43     while(scanf("%lld%lld",&a,&b)!=EOF){
44         if(ab)
45             swap(a,b);
46         ll ans = get(a) - get(b-1LL);
47         printf("%lld\n",ans);
48     }
49     return 0;
50 }