P2657题解

· · 个人记录

这道题是典型的数位dp，考虑记忆化搜索，dp[i][j]表示的是没有上界限制且没有前导零时以i为长度的最高位为j时的windy数的数量，然后进行搜索，在搜索到无上界和前导零时记录答案，具体解释参考AC代码中的注释

#include<bits/stdc++.h>
using namespace std;
int a,b; 
int dp[10][10],bord[10];//dp[i][j]表示无限制条件下的windy数数量，bord表示上界 
int dfs(int len,int last,bool limit,bool zero){//len表示所搜索的位数，last表示所搜索的位数的前一位的数字大小，limit表示是否为上界，zero表示该位是否为前导零 
    if(len==0) return 1;
    if(!limit&&!zero&&dp[len][last]!=-1) return dp[len][last];//若之前统计过答案则直接返回 
    int sav,maxi=(limit?bord[len]:9),ans=0;
    for(int i=0;i<=maxi;i++){
        if(abs(i-last)<2) continue;//判断是否符合前一位与该位差值绝对值至少为2 
        sav=i;
        if(zero&&i==0) sav=-256;
        ans+=dfs(len-1,sav,(limit&&(i==maxi)),(sav==-256));
    }
    if(!limit&&!zero) dp[len][last]=ans;//记录答案 
    return ans;
}
int solve(int x){
    memset(bord,0,sizeof(bord));
    int cnt=0;
    while(x){//分解上界 
        bord[++cnt]=x%10;
        x/=10;
    }
    memset(dp,-1,sizeof(dp));//注意初始化 
    return dfs(cnt,-256,true,true);//注意是从高位向低位搜索，所以需要初始化为达到上界（即limit为true） 
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.sync_with_stdio(false);
    cin>>a>>b;
    cout<<solve(b)-solve(a-1)<<endl;//运用前缀和的思想实现区间查询 
}

在写完这个记忆化搜索后，我们可以在题解里找到想到用正向循环的办法进行求解这道题，所以我在这里给出另外一种做法，即初始化dp数组然后再正向遍历求解，具体解释参考AC代码：

#include<bits/stdc++.h>
using namespace std;
int a,b;
int dp[10][10],bord[10];//dp定义与上个解法相同 
int solve(int x){
    memset(bord,0,sizeof(bord));
    int cnt=0,ans=0;//cnt表示长度，ans为最终答案 
    while(x){
        bord[++cnt]=x%10;
        x/=10;
    }
    //从这里开始分为三个部分进行求解
    //part 1:长度<cnt时一定在区间内，直接加 
    for(int i=1;i<=cnt-1;i++){
        for(int j=1;j<=9;j++){//注意循环从1开始 
            ans+=dp[i][j];
        }
    }
    //part 2:长度=cnt但最高位<bord[cnt]时，一定在区间内，直接加 
    for(int i=1;i<bord[cnt];i++){
        ans+=dp[cnt][i];
    }
    //part 3:长度=cnt且最高位达到上界，则向下搜索，将剩余符合条件的情况加入答案 
    for(int i=cnt-1;i>=1;i--){
        for(int j=0;j<=bord[i]-1;j++){//循环到当前位的上界 
            if(abs(j-bord[i+1])>=2) ans+=dp[i][j];
        }
        if(abs(bord[i+1]-bord[i])<2) break;//上界为已确定的数字，故若已确定的数字不为windy数则无需再遍历，直接break 
    }
    return ans;
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.sync_with_stdio(false);
    cin>>a>>b;
    for(int i=0;i<=9;i++) dp[1][i]=1;//由样例1可得：0,1,2,3,4,5,6,7,8,9都为windy数 
    for(int i=2;i<=10;i++){//数据量只到2e9所以遍历长度为10的windy数数量 
        for(int j=0;j<=9;j++){
            for(int k=0;k<=9;k++){
                if(abs(j-k)>=2) dp[i][j]+=dp[i-1][k];//若前一位与当前位的数字差>=2时，转移状态 
            }
        }
    }
    cout<<solve(b+1)-solve(a)<<endl;//注意与上题的区别 
    return 0;
}

希望能够帮到大家理解数位dp