基础数位DP小结


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表示,脑子还是不够活。



原文地址:https://www.cnblogs.com/yutingliuyl/p/6907960.html