【算法介绍】数位DP
算法简介:出发!火之国
数位DP,字面意思上来讲,就是按位做 DP,他的原理是基于类似于前缀和的思想,统计 0 ~ n 这部分的某种数字然后利用前缀和思想求出一段区间内某种数字的算法。
算法演示:以燔燎铸名
说实话,这是一个随机应变的算法,要更据题目给的数字用合适的方法计算数字,这里只能给出一点基础的建议。
我们思考,对于一个 $n$ 我们要制造出小于等于它的数字,怎么办?由于高位对于地位有绝对压制, 所以说如果当前位是 $P$ ,那么如果我选了数字 $i(i < P)$ ,那么往后的我们就可以随便选,如果 $i = P$ 我们还得继续考虑。
其次就是前导零。对于前导零我们还得开一个标记记录,如果前导零的标记还在,但是我们选了0,那这个是不算数的。
模板大概就是:
1 | int dp[50]; // DP数组 |
详细的用法还得自己体会,建议看下面的题目。
算法实战:荣花与炎日之途
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 祝馀宫!
评论