洛谷 P2657 [SCOI2009] windy 数

题目传送门

解题思路:

简单的数位DP,注意处理好前导0就行.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 
 7 using namespace std;
 8 
 9 int s[11],f[11][11],u;
10 long long a,b;
11 
12 inline long long dfs(int d,int p,bool qd,bool li) {
13     if(d > u) return 1;
14     if(!li && f[d][p] != -1) return f[d][p];
15     long long ans = 0;
16     int res = li ? s[u-d+1] : 9;
17     for(int i = 0;i <= res; i++) {
18         if(abs(p - i) < 2) continue;
19         if(qd && i == 0) ans += dfs(d + 1,-2,1,li && (i == res));
20         else ans += dfs(d + 1,i,0,li && (i == res));
21     }
22     if(!qd && !li) f[d][p] = ans;
23     return ans;
24 }
25 
26 inline long long solve(int x) {
27     u = 0;
28     while(x) {
29         s[++u] = x % 10;
30         x /= 10;
31     }
32     memset(f,-1,sizeof(f));
33     return dfs(1,-2,1,1);
34 }
35 
36 int main() {
37     scanf("%lld%lld",&a,&b);
38     printf("%lld",solve(b) - solve(a-1));
39     return 0;
40 }