UESTC 250 windy数数位dp

题目链接1 #include<bits/stdc++.h>2 using namespace std;3 #define mem1(a) memset(a, -1, sizeof(a))4 #define ll long long5 int dp[20][20], digit[20], len;6 ll dfs(int len, int pre,...

weixin_30653023

67人浏览 · 2015-12-10 10:48:00

weixin_30653023 · 2015-12-10 10:48:00 发布

题目链接

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem1(a) memset(a, -1, sizeof(a))
 4 #define ll long long
 5 int dp[20][20], digit[20], len;
 6 ll dfs(int len, int pre, bool fp, bool first) {     //first表示前面的数是否全部为0， pre是前一个数
 7     if(!len)
 8         return 1;
 9     if(!first&&!fp && dp[len][pre]!=-1)
10         return dp[len][pre];
11     int ret = 0, maxx = fp?digit[len]:9;
12     for(int i = 0; i<=maxx; i++) {
13         if(!first)
14             if(abs(i-pre)<2)
15                 continue;
16         ret += dfs(len-1, i, fp&&i == maxx, first&&i==0);
17     }
18     if(!fp&&!first)
19         return dp[len][pre] = ret;
20     return ret;
21 }
22 int cal(int n) {
23     len = 0;
24     while(n) {
25         digit[++len] = n%10;
26         n/=10;
27     }
28     return dfs(len, 0, true, true);
29 }
30 int main()
31 {
32     int a, b;
33     mem1(dp);
34     while(~scanf("%d%d", &a, &b)) {
35         printf("%d\n", cal(b)-cal(a-1));
36     }
37 }