HDU 3555 Bomb
dp[i][0] 表示含 i 位数的方案总和。
sp[i][0] 表示对于位数为len 的 num 在区间[ 10^(i-1) ， num/(10^(len-i)) ] 内的方案数。
对于dp[i][3]，dp[ i ][ 0 ]表示位数为 i 且含49的方案数，dp[ i ][1]表示位数为 i 且不含49 且末尾不为4的方案数，dp[ i ][2]表示位数为 i 且不含49且末尾为4的方案数。
对于sp[ i ][3]，意义相同，只不过要判断i-1位时的上界出现在哪一种情况内，在讨论当前位上数字的大小。
HDU 2089 不要62
dp[ len ][ 2 ] [ 2 ][ 2 ] len表示数的长度，第二维表示在此位上是否到达上界，第三维表示前一位是否为 6 ，第四维表示前面是否出现62 或 4 。
记忆化搜索，真心是模板题。数据也很弱，包搜才300+ms。
HDU 3652 B-number
与上面的题类似吧，同属模板一级的题。
dp[ len ][2][2][2][13] len表示数的长度，第二维表示在此位上是否到达上界，第三维表示前一位是否为 1 ，第四维表示前面是否出现13，第五维标记当前状态的对13取余的余数 。
CF 55D Beautiful Number
虽说不是自己做的，但是学到了不少东西。对于DP的两种写法——递推和记忆化搜索也略有感悟。困了，明天补题解。
————————————————————
首先科普一个知识点，设a，b，c，若a%b == 0,b%c == 0,则必有a%c == 0。
换言之，c = LCM(a,b),若x%c == 0，则必有x%a == 0 ,x%b == 0。反之，若x%c != 0,则 x 必不能同时被a，b整除。
对于 1 到 9 这九个数的LCM为2520，而1 到 9这几个数的任意组合则有48个不同的最小公倍数。
也就是说只需记录（x % 2520）和 出现的数字的最小公倍数。
另外还需位数和是否到达上界，则dp数组为 dp[ 2 ][ len ][2520][49]。
第一维表示是否到达上界。
第二维表示要求数字的长度。
第三位表示对2520的余数。
第四维表示前面出现的数对应着哪个最小公倍数。除去48个最小公倍数外，还应记录 0 的情况。
总的时间复杂度即为 2*len*2520*49。
对于递推：
dp表示前 i 位的情况。即由前 i 位的情况推出 i+1 的情况。
显然，当前面的数变了之后，后面的也必然会改变。
所以每次都会从头到尾重新递推计算一遍。
时间上承受不了。
对于记忆化搜索：
dp记录第 i 位到 len位的状态。即由子状态回溯得到母状态。
显然此时当前面的数改变了之后并不影响后面的状态。
对于此题，每当给出一个新的x，那些到达上界的情况会改变，而没有到达上界的情况不会发生改变。
所以对于新的x，我们只需要计算到达上界的那些情况即可。
时间复杂度降到了len*2520*49。
完全可以过了。
URAL Amount of Degrees
表示真没看懂题，第一次在Ural上看见这么坑的题。
求在[X, Y]中的数的B进制只有K为不为0，且这K位必须为1。我只想问一下题目中哪句说为1。
剩下的就是简单的模板了。
基础数位DP小结,布布扣,bubuko.com
基础数位DP小结
原文：http://blog.csdn.net/zmx354/article/details/24323993
