登录
← 返回首页 | 代码片段 › 5 动态规划 › 5.3 数位DP › 数位DP / 搜索
JSON MD

5.3 数位DP

数位DP (Windy数) dfs
27 行
CPP JSON
【数位DP (Windy数)(dfs)】 数位 DP 模板,在数字的十进制/二进制位上做记忆化搜索。 核心函数: int dfs(int len,int up,int ok) — 深度优先搜索遍历 int sovle(int x) — 核心算法函数 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:与数字各位有关的计数/最优化问题
C++ 26 行 CPP
#include<cstring>
#include<cstdio>
#include<cmath>
#define R register int
using namespace std;
int a,b,l,num[12],dp[12][10];
inline int dfs(int len,int up,int ok){
    R i,ed,ans=0;
    if(len<1)return 1;
    if(!ok&&~dp[len][up]&&up!=-7)return dp[len][up];
    ed=ok?num[len]:9;
    for(i=0;i<=ed;i++)if(abs(i-up)>=2)
        ans+=dfs(len-1,(!i&&up==-7)?up:i,ok&&(i==ed));
    if(!ok&&up!=-7)dp[len][up]=ans;
    return ans;
}
inline int sovle(int x){
    l=0;
    while(x)num[++l]=x%10,x/=10;
    return dfs(l,-7,1);
}
int main(){
    scanf("%d%d",&a,&b);
    memset(dp,-1,sizeof(dp));
    printf("%d",sovle(b)-sovle(a-1));
}
数位DP (Windy数) dp
37 行
CPP JSON
【数位DP (Windy数)(dp)】 数位 DP 模板,在数字的十进制/二进制位上做记忆化搜索。 核心函数: int dpp(int len) — 核心算法函数 int sovle(int x) — 核心算法函数 int sakura(无参数) — 后缀数组 复杂度:时间复杂度取决于状态数和转移复杂度 适用场景:与数字各位有关的计数/最优化问题
C++ 36 行 CPP
#include<cstdio>
#include<cmath>
#define R register int
using namespace std;
int i,j,k,a,b,l,ans,num[12],dp[12][10];
inline int dpp(int len){
    ans=0;
    for(i=1;i<len;i++)
        for(j=1;j<10;j++)
            ans+=dp[i][j];
    for(j=1;j<num[len];j++)ans+=dp[len][j];
    for(i=len-1;i>0;i--){
        for(j=0;j<num[i];j++)
            if(abs(num[i+1]-j)>=2)ans+=dp[i][j];
        if(abs(num[i]-num[i+1])<2)break;
    }
    if(!i)ans++;
    return ans;
}
inline int sovle(int x){
    l=0;
    while(x)num[++l]=x%10,x/=10;
    return dpp(l);
}
inline int sakura(){
    scanf("%d%d",&a,&b);
    for(i=0;i<10;i++)dp[1][i]=1;
    for(i=2;i<11;i++)
        for(j=0;j<10;j++)
            for(k=0;k<10;k++)
                if(abs(j-k)>=2)
                    dp[i][j]+=dp[i-1][k];
    printf("%d",sovle(b)-sovle(a-1));
}
int QAQWQ=sakura();
int main(){}
已复制