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}$。更加简洁。