洛谷 P2657 [SCOI2009]windy数（数位DP）

题目链接：https://www.luogu.com.cn/problem/P2657

一道细节比较多的数位DP。

第一个细节：对于有前导零的数字的处理是一个细节。数位DP模板是不能认为它们是windy数的。因为DFS中的pre有问题。那可以把pre在一开始设成一个较小的数，然后在DFS的过程中，如果是有前导零的情况，那么就仍是那个较小的数，否则换成它真正的pre。

第二个细节：我们发现在处理的过程中，我们一直把1也当成windy数，但事实上它并不是，但这并不影响结果，前后一减不就没了吗？

dp[len][pre]

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 int a[20];
 8 int dp[20][20];
 9 int DFS(int pos,int pre,int limit,int lead){
10     if(pos==0) return 1;
11     if(!limit&&!lead&&dp[pos][pre]!=-1) return dp[pos][pre];
12     int up=limit?a[pos]:9;
13     int ans=0;
14     for(int i=0;i<=up;i++){
15         if(abs(i-pre)<2) continue;
16         int p=i;
17         if(lead&&i==0) p=-100;//前导零情况pre的处理 
18         ans+=DFS(pos-1,p,limit&&i==a[pos],lead&&i==0); 
19     }
20     if(!lead&&!limit) dp[pos][pre]=ans;
21     return ans;
22 }
23 int solve(int x){
24     int len=0;
25     memset(dp,-1,sizeof(dp));
26     while(x){
27         a[++len]=x%10;
28         x/=10;
29     }
30     return DFS(len,-100,1,1);//注意初始的pre 
31 }
32 int main(){
33     int A,B;
34     scanf("%d%d",&A,&B);
35     printf("%d",solve(B)-solve(A-1));
36     return 0;
37 }

AC代码