数位dp(未完工） 前言好像好久没写blog了还是喜欢可爱的数位dp啊正文数位dp,是指一种专门用于解决区间范围内满足特定约束条件的数字统计问题的算法尤其适用于处理数值范围极大的场景。其核心是通过将数字按数位拆解结合记忆化搜索或迭代的动态规划方法从而迭代算出答案。本文使用记忆化搜索方式进行计算因为自认为更简单。数位dp模板依旧先上模板。先讲述一下流程判断是否到达边界。判断是否遍历过如果遍历过直接return。for循环从0到边界(看limit)。如果有条件不满足continue。累计迭代dfs如果没有前导0dp记录一下return ans。好了放个代码看一下吧。#includebits/stdc.h using namespace std; int o,p,a[15],dp[15][15][2][2]; int dfs(int now,int pre,int limit,int flag){ if(now0)return 1; if(dp[now][pre][limit][flag]!-1)return dp[now][pre][limit][flag]; int ans0; for(int i0;i(limit?a[now]:9);i){ if(!flagabs(i-pre)2)continue; ansdfs(now-1,i,limit(ia[now]),flag(i0)); } dp[now][pre][limit][flag]ans; return ans; } int init(int x){ int cnt0; while(x){ a[cnt]x%10; x/10; } memset(dp,-1,sizeof dp); return dfs(cnt,12,1,1); } int main(){ int o,p; cinop; coutinit(p)-init(o-1)\n; }好了做几道题目练练手吧。。。P2602 [ZJOI2010] 数字计数依旧先放部分代码int dfs(int now,int limit,int flag,int d,int sum){ if(now0)return sum; if(dp[now][limit][flag][sum]!-1)return dp[now][limit][flag][sum]; int ans0; for(int i0;i(limit?a[now]:9);i){ int tmpsum; if(id(d!0||!flag))tmp; ansdfs(now-1,limit(ia[now]),flag(i0),d,tmp); } dp[now][limit][flag][sum]ans; return ans; } signed main(){ int o,p; cinop; for(int i0;i10;i)coutinit(p,i)-init(o-1,i) ; }这里其实只要枚举个数字剩下就和上一题一样了。P8764 [蓝桥杯 2021 国 BC] 二进制问题int dfs(int now,int limit,int sum){ if(now0)return sumk; if(dp[now][limit][sum]!-1)return dp[now][limit][sum]; int ans0; for(int i0;i1;i){ if(limitia[now])break; ansdfs(now-1,limit(ia[now]),sumi); } dp[now][limit][sum]ans; return ans; } int init(int x){ int cnt0; while(x){ a[cnt]x%2; x/2; } memset(dp,-1,sizeof dp); return dfs(cnt,1,0); }这个只是要把原来的10进制改为2进制好了改一下就和模板一样了。P4124 [CQOI2016] 手机号码int dfs(int pos,int num,int rep,int f8,int f4,int frep,int f,string limit){ if(limit9999999999)return 0; if(f81f41)return 0; if(pos0){ if((frep1||rep3)(f8^f41||(f80f40)))return 1; else return 0; } if(!fdp[pos][num][rep][f8][f4][frep]!-1)return dp[pos][num][rep][f8][f4][frep]; int ans0; int k9; if(f)klimit[11-pos]-0; int l0; if(pos11)l1; for(int ik;il;i--){ ansdfs(pos-1,i,(numi?rep1:1),f8||(i8),f4||(i4),frep||(rep3),f(ik),limit); } if(!f)dp[pos][num][rep][f8][f4][frep]ans; return ans; }这里判断就很麻烦了首先要判断4与8有没有还要判断最大相等字串其他就差不多了只是处理麻烦了一点。P4127 [AHOI2009] 同类分布int dfs(int now,int sum,int st,int limit){ if(nowcntsum0)return 0; if(nowcnt)return st0summod?1:0; if(!limitdp[now][sum][st]!-1)return dp[now][sum][st]; int ans0; for(int i0;i(limit?a[cnt-now1]:9);i){ ansdfs(now1,sumi,(st*10i)%mod,i(limit?a[cnt-now1]:9)limit); } return limit?ans:dp[now][sum][st]ans; } int init(int x){ cnt0; while(x){ a[cnt]x%10; x/10; } int res0; for(mod1;mod9*cnt;mod){ memset(dp,-1,sizeof dp); resdfs(1,0,0,1); } return res; }这题搜索框架很简单但是如何记录dp呢st最大会达到1e18肯定不可能的。所以我们可以使用取模。于是我们可以枚举mod来叠加从而算出答案。P3413 SAC#1 - 萌数CF55D Beautiful numbers结语hhh好好玩啊