G - windy数 解题报告

题目链接：https://vjudge.net/contest/381753#problem/G

知识预备：数位DP
数位DP的题目往往是这样的：
给定一个闭区间[L,R],求这个区间中满足"某种条件"的数的总数量。
数位DP技巧：
技巧1：[X,Y] -> f(Y)-f(X-1)
把统计[L,R]范围满足条件的数的个数转化为统计[1,N]内满足条件的数的个数，这样，f([L,R]) = f([1,R])-f([1,L-1]) , 那么接下来讨论问题只需要考虑上边界就行了。
技巧2：树的方式来考虑

代码实现用dfs从高位到低位枚举
解题思路：
对于这道题，dfs需要记录的状态有：
1.现在枚举第几位
2.前面一位的数字是多少
3.这一位可以填哪些数字

位置pos有两种可能性：
1.如果pos前面某一位已经小于上限数字所对应位置的数字，那么这一位可以填0-9
2.如果pos前面每一位都与上限数字所对应位置的数字相同，那么这一位只能填0-
因此，维护前面每一位是否与上限所对应位置的数字相同，就可以得到pos位枚举数字范围。
然后用一个dp[pos][pre_num]来记录，避免重复调用。
这里需要注意，！flag的情况下和flag情况下；有前导0和无前导0情况下，dp[pos][pre_num]是不同的。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[30];
int dp[30][30];
int dfs(int pos, int pre, bool flag, bool lead)
{
    //lead用于判断从高位到低位枚举时有没有前导0，
    //如对1232
    //当前面几位枚举的都是0时，后面一位的枚举是不受前面一位限制的，
    //因为如果前面几位都是0，就相当于前几位是不存在的，
    //所以才有： if( abs(i-pre) >=2 || lead)
    if(!pos) return 1;
    if(dp[pos][pre] != -1&&!flag&&!lead) return dp[pos][pre];
    int ans = 0, max_num;
    if(flag) max_num = a[pos]; else max_num = 9;
    for(int i = 0; i <= max_num; i++) {
        if(abs(i-pre) >= 2 || lead) {
            ans+=dfs(pos-1, i, flag&&(i==a[pos]), lead&&(i==0));
        }
    }
    if(!flag&&!lead) dp[pos][pre] = ans;
    return ans;
}
int solve(int x)
{
    int len = 0;
    while(x) a[++len]=x%10, x/=10;
    memset(dp, -1, sizeof(dp));
    return dfs(len, -2, 1, 1);
}
int main()
{
    int l, r;
    cin >> l >> r;
    cout << solve(r)-solve(l-1) << endl;
}