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。
剩下的就是简单的模板了。
HDU 4389 X mod f(x)
dp[len][ i ][ j ][ k ] 第一维表示长度。第二维表示各位之和。第三维和第四维的意义表示x % j == k。
之前的几个题看别人的代码始终没搞明确为神马dp数组里面没有表示是否达到上限的一维。
今天做这个题最终顿悟了。
达到上限仅仅会造成后面的几项取不到。是未到上限的情况的子集。
所以我们仅仅要处理出未到的情况就可以。
HDU 4352 XHXJ's LIS
必需要说一下关于最朴素的LIS的两种算法。
一种是复杂度为 o(n^2)。len[i]通过与前 i-1的比較来更新，不多说了。
还有一种是复杂度为 o(n*log(n))。数组c[len] 表示当更新到第 i 位时。长度为len的位置处的最小值。
当更新到num[ i ]仅仅需二分查找最小的满足c[site] >= num[i]的site。然后更新c[ site ]。
若未找到则仅仅需将num[ i ]放入c[ ]末尾。
显然此题仅仅需标记当dfs到site时，c[ ] 里面记录了那些元素就可以。
HDU 4737 F(x)
首先计算出F(A)。然后对site 和 F(A) dfs，入门级别的题吧。刷起来蛮顺手的。
ZOJ 3416 Balanced Number
dp[ site ][piv][sum] 表示位置。对称轴。累加和。
開始时。dp[site][L][piv][R] L表示左边的和，R表示右边的和。MLE了两次。事实上能够用sum = L-R表示，脑子还是不够活。