Codeforces Round #714 Add One DP

题意

定义一种操作是把当前值的每一位数字都+1。比如$1912$经过一次操作之后就是$21023$。

现在给你一个n,问你做了m次上述操作后,长度是多少。


题解

唉。读错题,以为要求精确值。老文盲了。但不管怎么读,读来读去都是DP(因为即使要求精确值,也需要上一位的长度)。

解法一

定义$dp_i$表示从1开始,做m次操作后的长度。

那么显而易见对于$0\leq{i}\leq{8}$都有$dp_i=1$。

对于$i\geq{9}$,我们首先可以+9,这样原先的1就变成了10。于是问题转化成了对第一位的1做$i-9$次操作和对第二位的0做$i-9$次操作。显然,第一位操作的结果等于$dp_{i-9}$。

对于第二位因为是0,所以没办法只能+10再放出去一位1,而新的一位1的操作次数和长度是$dp_{i-9-10}$。如此不断操作,直到剩下的操作次数不超过10,无法新放出一位。最后得到如下定义:

$$dp_i=1+dp_{i-9}+dp_{i-9-10}+dp_{i-9-10-10}+...$$

所以最后再维护10个前缀和,以保证能快速的求出$i-9-10$往前的全部和。

解法二

在上一个解法中,第二位是0的时候选择+10放出新的一位数字。但其实没必要,直接做一次操作,使0变成1即可。于是得到$dp_i=dp_{i-9}+dp_{i-10}$。更加简洁。


代码

Submission #112780116 - Codeforces
Codeforces. Programming competitions and contests, programming community
蜀ICP备19018968号