求救,记忆化搜索形式的数位DP
查看原帖
求救,记忆化搜索形式的数位DP
575802
Technablode楼主2021/10/27 23:28
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int l,r,num[15],f[20][2][20][2];
int dfs(int location,bool limit,int pre,bool zero){
    if(!location) return 1;
    if(f[location][limit][pre][zero]!=-1) return f[location][limit][pre][zero];
    int temp=9;
    if(limit) temp=num[location];
    int ans=0;
    for(int i=0;i<=temp;i++){
        if(abs(i-pre)<=2&&!zero) continue;
        else{
            ans+=dfs(location-1,limit&&(i==num[location]),i,0);
        }
    }
    f[location][limit][pre][zero]=ans;
    return ans;
}
int solve(int x){
    memset(f,-1,sizeof f);
    int location=0;
    while(x){
        num[++location]=x%10;
        x/=10;
    }
    return dfs(location,1,0,1);
}
int main(){
    scanf("%d%d",&l,&r);
    printf("%d %d\n",solve(r),solve(l-1));
}
2021/10/27 23:28
加载中...