总结数位DP算法.doc

1、数位dp是一种计数用的dp, 般就是要统计一个区间le,ri内满足一些条件数的个 数。比如，1,10000中统计不含有4的数。所谓数位dp，字面意思就是在数位上进行dp咯。就是对数字每一位每一位递推此类题目最基本的暴力方法：1. for (inti=le;i=ri;i+)2. if (Check(i)ans+;而数位DP就是从最低(高)位起，一位一位的放数字，然后记忆化一下，累加一下有两种方法，一是递推，二是记忆化搜索一，记忆化搜索：思路来自：数位dp总结 之 从入门到模板假设题目要求是不含有62的数状态定义：dpospre表示当前枚举到pos位置，且pos+1位的数字是pre，此时满足题意的

2、数字的个数(也即是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,当然这是看题意的，有 时候题目不

3、要求，可以直接省去好了，看模板：1. typedef long long ll;2. int a20;3. lldp20state; /不同题目状态不同4. lldfs( int pos, /*state 变量 */ , bool lead /* 前导零 */ , bool limit /* 数位上界变量 */ )/不是每个题都要判断前导零5. 6. /递归边界，既然是按位枚举，最低位是0，那么pos=-1说明这个数我枚举完了7. if (pos=-1) return 1;/*这里一般返回1,表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到po

4、s位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */1./第二个就是记忆化(在此前可能不同题目还能有一些剪枝)if (!limit & !lead & dpposstate!=-1)return dpposstate;/*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/int up=limit?apos:9

5、; /根据limit判断枚举的上界up;这个的例子前面用 213讲过了ll ans=0;/开始计数for (int i=0;i=up;i+)/枚举，然后把不同情况的个数加到ans就可以了if ().else if ().ans+=dfs(pos-1, /* 状态转移 */ ,lead & i=0,limit & i=apos) /最后两个变量传参都是这样写的/*这里还算比较灵活，不过做几个题就觉得这里也是套路了大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目要求数位上不能有62连续出现，那么就是stat

6、e就是要保存前一位pre,然后分类，前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/计算完，记录状态if (!limit & !lead) dpposstate=ans;/*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需 要考虑lead，这里就是lead就完全不用考虑了 */return ans;ll solve(ll x)int pos=0;while (x) /把数位都分解出来apos+=x%10; /个人老是喜欢编号为0,pos),看不惯的就按自己习惯来，反正注意数位边界就行x/=10;return dfs(pos-1 /*从最高位开始

7、枚举*/ , /* 一系列状态 */ ,true , true ); /刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛int main()42.IIle,ri;43.while (scanf( %lld%lld，&le,&ri)44.45./初始化dp数组为-1,这里还有更加优美的优化，后面讲46.printf( %lldn ,solve(ri)-solve(le-1);47.48. 那个 if（!limit & Head & dpposstate!=-1） returndpposstate;limit的数字必须要枚举，不能直接返回，每次都要算虽然这会导致重复，但这可以

8、解决状态冲突，而且重复计算的数字也很少 举例如下：题目：不能出现连续的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就是在

9、30003999的符合题意的个数还要个数组ai保存第i位的数字，如213，a1=3，注意是从右往左数（下面是从1开始数起了）这样状态定义的能更加方便，可以预处理，因为当一个数字的第一位比题目要求的第一位小后，后面的几位能 000.999. 如4269，如果第一位枚举3 ，那么后三位可以任取模板如下：..for (int i=1;i=7;i+)/ 枚举位数for (int j=0;j10;j+)/枚举第i位可能出现的数for (int k=0;k10;k+) /枚举第i-1位可能出现的数if (j!=4&!(j=6&k=2)/ 符合题意的条件dpij+= dpi-1k

10、;9.10.11.以HDU 2089，解释怎么算出答案（不含4, 62的数字）1.#include 2.#include 3.#include 4.#include 5.usingnamespace std;6.intd1010,digit10;7.d【ij表示有i位数字，且第一位是j的数字的满足题意的数量8.voidinit()9.10.d00=1;11.for (int i=1;i=7;i+)12.for (int j=0;jv=9;j+)13.for (int k=0;k=1;i-)27.for (int j=0;jdigiti;j+)/ 注意不是小于等于28.if (j!=4&!(j=

11、2&digiti+1=6)29.ans+=dij;30.31.if (digiti=4|(digiti+1=6&digiti=2)32.break ;33.34.return ans;35.36.intmain( int argc, char const *argv)37. 38.int n,m;39.init();40.while (cinnm,n+m)41.coutvsolve(m+1)-solve(n)vvendl;/由于要找n,m,而solve函数找的范围为n,所以传参的时候应该特别注意42.return 0;43. 假设一个数3229得出00000999 的个数10001999 的个

12、数20002999 的个数000099 的个数100199 的个数0099 的个数1019的个数08 的个数累加就是答案了所以该区间是0,n）是取不到的n的，注意计算的时候要加一个 1 下面是一些题目：HDU 2089 不要 62 和 4HDU 3555含49的数HDU 3652含13且可以被13整除codeforces 55d A 一个数字可以被它所有非零数整除的个数POJ 3252 Rou nd NumbersHDU 4734 F（x）HDU 3709 Bala need NumberHYSBZ 1799 self 同类分布URAL 1057 Amou nt of Degrees *HDU 4507吉哥系列故事一一恨 7不成妻*总结：可能要用到的数位 DP的题目类型：110A18，求某区间（很大），有特定要求的数字的个数 如求mod求和，可以整除各位数，不出现某些数 框架：in t DFS(i nt pos,)DFS 位一位放数字，求