2022年总结数位DP算法汇编 .pdf

数位 dp 是一种计数用的dp，一般就是要统计一个区间le,ri 内满足一些条件数的个数。比如， 1,10000 中统计不含有4 的数。所谓数位 dp，字面意思就是在数位上进行dp咯。就是对数字每一位每一位递推此类题目最基本的暴力方法：1.for ( int i=le;i=ri;i+) 2.if (Check(i) ans+; 而数位 DP 就是从最低 (高)位起，一位一位的放数字，然后记忆化一下，累加一下有两种方法，一是递推，二是记忆化搜索一，记忆化搜索：思路来自： 数位 dp 总结之从入门到模板假设题目要求是不含有62 的数状态定义： dpospre 表示当前枚举到pos位置，且 pos+1 位的数字是 pre，此时满足题意的数字的个数(也即是 pre=6 时， pos该位置不能放2) 还要个数组 ai保存第 i 位的数字，如213，a0=3，注意是从右往左数有个问题是枚举第pos位数时，此位置放数字的范围要判断一下，比如题目给出在1,894 枚举的时候要判断是否在894 以内比如，213，第一位放了 2，那么第二位就只能放01，所以模板中用了个limit 判断pos前的几位数字是否与n 一样， true 的话只能枚举0apos，false 就是 09，不然比题目要求的213 大了还有个问题是前导0 的问题，假如枚举5 位数，你放的时候前2 位都是 00，那数字不变成 3 位了嘛，所以需要个lead保存前几位是否都是0，当然这是看题意的，有时候题目不要求，可以直接省去好了，看模板：1.typedeflonglong ll; 2.int a20; 3.ll dp20state;/ 不同题目状态不同4.ll dfs(int pos,/*state变量 */ , bool lead/* 前导零 */ , bool limit/* 数位上界变量 */ ) /不是每个题都要判断前导零5. 6./ 递归边界，既然是按位枚举，最低位是0，那么 pos=-1说明这个数我枚举完了7.if (pos=-1) return 1; /* 这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos 位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 8./ 第二个就是记忆化( 在此前可能不同题目还能有一些剪枝)9.if (!limit & !lead & dpposstate!=-1) return dpposstate; 10./* 常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/11.int up=limit?apos:9;/ 根据 limit判断枚举的上界up; 这个的例子前面用213 讲过了12. ll ans=0; 13./ 开始计数14.for ( int i=0;i=up;i+)/ 枚举，然后把不同情况的个数加到ans 就可以了15. 16.if () . 17.elseif (). 18. ans+=dfs(pos-1,/* 状态转移 */ ,lead & i=0,limit & i=apos) / 最后两个变量传参都是这样写的19./* 这里还算比较灵活，不过做几个题就觉得这里也是套路了20.大概就是说，我当前数位枚举的数是i ，然后根据题目的约束条件分类讨论21.去计算不同情况下的个数，还有要根据state变量来保证i 的合法性，比如题目22.要求数位上不能有62 连续出现 , 那么就是 state就是要保存前一位pre, 然后分类，23.前一位如果是6 那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/24. 25./ 计算完，记录状态26.if (!limit & !lead) dpposstate=ans; 27./* 这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑 lead ，这里就是lead就完全不用考虑了*/28.return ans; 29. 30.ll solve(ll x) 31. 32.int pos=0; 33.while (x) / 把数位都分解出来34. 35. apos+=x%10;/ 个人老是喜欢编号为0,pos),看不惯的就按自己习惯来，反正注意数位边界就行36. x/=10; 37. 38.return dfs(pos-1/* 从最高位开始枚举*/ , /* 一系列状态 */, true , true); / 刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0 嘛39. 40.int main() 41. 42. ll le,ri; 43.while (scanf(%lld%lld,&le,&ri) 44. 45./ 初始化 dp 数组为 -1, 这里还有更加优美的优化, 后面讲名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 46. printf(%lldn,solve(ri)-solve(le-1); 47. 48. 注意：那个 if(!limit & !lead &dpposstate!=-1) return dpposstate; limit 的数字必须要枚举，不能直接返回，每次都要算虽然这会导致重复，但这可以解决状态冲突，而且重复计算的数字也很少举例如下：题目：不能出现连续的11 (11、112、211 都是不合法的 ) 那么我们开始枚举：要枚举 3 位数，已经枚举了两位01_ ，要枚举最后一位，此时状态为d01 即：在枚举个位，且前一位为1，那么显然得出d01=9 开始新的一轮枚举，枚举到11_ ，此时状态也是d01 因为已经有 9 这个值了，所以返回了，但很明显答案是0，是错的当然可以多开一维防止状态冲突可以看看数位DP 模板题： HDU 2089 不要 62 数位 DP .二，递推方法思路来自： 初探数位 dp状态定义： dij 有 i 位数字，且第一位为j，在 0j-1 + 000.999 的符合题意的个数，如d43 就是在 30003999 的符合题意的个数还要个数组 ai保存第 i 位的数字，如 213，a1=3，注意是从右往左数 （下面是从 1开始数起了）这样状态定义的能更加方便，可以预处理，因为当一个数字的第一位比题目要求的第一位小后， 后面的几位能000.999. 如 4269，如果第一位枚举3 _ _ _ ，那么后三位可以任取模板如下：1.for ( int i=1;i=7;i+) / 枚举位数2. 3.for ( int j=0;j10;j+)/ 枚举第 i 位可能出现的数4. 5.for ( int k=0;k10;k+)/ 枚举第 i-1位可能出现的数6. 7.if (j!=4&!(j=6&k=2) / 符合题意的条件8. dpij += dpi-1k; 9. 10. 11. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 以 HDU 2089 ，解释怎么算出答案（不含4，62 的数字）1.#include 2.#include 3.#include 4.#include 5.usingnamespace std; 6.int d1010,digit10; 7./dij 表示有 i 位数字，且第一位是j 的数字的满足题意的数量8.void init() 9. 10. d00=1; 11.for ( int i=1;i=7;i+) 12.for ( int j=0;j=9;j+) 13.for ( int k=0;k=1;i-) 27.for ( int j=0;jnm,n+m) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 41. coutsolve(m+1)-solve(n)endl;/ 由于要找 n,m,而 solve函数找的范围为n, 所以传参的时候应该特别注意42.return 0; 43. 假设一个数 3229 得出00000999 的个数10001999 的个数20002999 的个数000099 的个数100199 的个数0099 的个数1019 的个数08 的个数累加就是答案了所以该区间是 0,n) 是取不到的 n 的，注意计算的时候要加一个1 下面是一些题目：HDU 2089 不要 62 和 4 HDU 3555 含 49 的数HDU 3652 含 13 且可以被 13整除codeforces 55d A 一个数字可以被它所有非零数整除的个数POJ 3252 Round Numbers HDU 4734 F(x) HDU 3709 Balanced Number HYSBZ 1799 self 同类分布URAL 1057 Amount of Degrees * HDU 4507 吉哥系列故事 恨 7 不成妻 * 总结：可能要用到的数位DP 的题目类型：11018，求某区间（很大），有特定要求的数字的个数如求 mod，求和，可以整除各位数，不出现某些数. 框架：int DFS(intpos,.) /DFS 一位一位放数字， 求出答案， 函数的参数保存题目要求的状态int solve(int n) / 把 n 一位一位拆分，求出1,n 的符合要求的值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 难点：定义好状态！1.dp 状态要找好，不要出现状态重叠现象，注意前导0 有没有影响2.题目有求和 sum，可能会很大，但可以转化为保存sum对一个数求 mod 的值3.有时候 dp 状态定义不好可能要求每次DFS 都要 memset一下，换换思路想想通用的状态定义，如sum 从加法改为减法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -