【洛谷P2657】[SCOI2009] windy数

最近学习了一下数位DP

感觉记忆化搜索是比较好理解的

这篇博客对我有一定的启发 https://www.cnblogs.com/zbtrs/p/6106783.html

总结了一下：

用数位DP的题目：

形如“问在x到y的整数中满足性质……的数的个数”

套路：

main函数一般是这样的

设max为上限值，即我们要统计 max之前的满足性质的数的个数

为了使搜到的数都满足 x<max

所以我们在搜索时定义一个bool型变量shangxian，表示搜到当前数位时前面的数位是否是沿着上限值

例如：上限max为54123

第一位时shangxian=true 搜0,1,2,3,4,5

若第一位搜到了0,1,2,3,4，下一位shangxian=false

若第一位搜到了5，下一位shangxian=true

若shangxian=false 该位枚举0~9，且向下递归时shangxian一直为false

若shangxian=true 该位枚举0~max[i],当该位搜到max[i]时，下一位shangxian=true，否则

Shangxian=false

windy数

显然这是一道数位DP的题

要注意的地方是前导全零时的状态转移

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 #define abs(i) ((i)>0?(i):(-i))
 7 int a,b,maxx[20],dp[20][10];　　//dp[i][j]前i位 第i-1位是j的方案数
 8 int dfs(int len,int lastnum,bool shangxian,bool O){
 9     if(len==0) return O^1;
10     if(!shangxian&&dp[len][lastnum])
11         return dp[len][lastnum];
12     int cnt=0,M=shangxian?maxx[len]:9;
13     for(int i=0;i<=M;i++){
14         if(!O&&abs(lastnum-i)<2) continue;　　　　//前面都是前导0，该位不受其限制
15         cnt+=dfs(len-1,i,shangxian&&i==M,O&&i==0);
16     }
17     if(!shangxian&&!O) dp[len][lastnum]=cnt;　　//前面都是前导0，不会限制到下一位，不能记忆化
18     return cnt;
19 }
20 int solve(int x){
21     memset(maxx,0,sizeof(maxx));
22     memset(dp,0,sizeof(dp));　　　　//注意要清空数组
23     int k=0;
24     while(x){
25         maxx[++k]=x%10;
26         x/=10;
27     }
28     return dfs(k,-10,1,1);
29 }
30 int main()
31 {
32     scanf("%d%d",&a,&b);
33     printf("%d",solve(b)-solve(a-1));
34     return 0;
35 }