猫猫与雪糕棒：最优操作次数的计算

题目描述/n/n猫猫有若干个雪糕棒排成一排，每个雪糕棒上有一个 $0/sim9$ 的数字，并且满足最左边的雪糕棒上写的数字不为 $0$。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 $n$。/n/n猫猫认为 $0$ 是美好的，所以她会尽可能把 $n$ 变成 $0$，也就是把所有雪糕棒都拿走。/n/n猫猫每次会进行一次操作。每次操作选择一个数字非 $0$ 的雪糕棒，并将其减 $1$。这之后，如果最左边有连续的一些数字为 $0$ 的雪糕棒（也即 $n$ 出现了前导 $0$），猫猫会把这些雪糕棒拿走。/n/n小老鼠会来捣乱，它会在某个时刻（可能是所有操作开始之前，也可能是猫猫任意一次操作之后）改变某个雪糕棒上的一个数字。小老鼠总共只能改变一个数字。/n/n小老鼠希望操作次数尽量多，猫猫希望操作次数尽量少，所以她想知道二者都使用最优策略时，她的操作次数。/n/n输入格式/n本题有多组数据。/n/n第一行一个正整数 $T$ 表示数据组数。/n/n对于每组数据：仅一行，一个正整数 $n$。/n/n输出格式/n共 $T$ 行，每行一个整数，表示答案。/n/n输入输出样例/n输入 #1/n/n2/n1100/n11332132121/n/n输出 #1/n/n11/n28/n/n说明/提示/n样例解释/n/n对于第一组数据，小老鼠可以一开始就将 $1100$ 变为 $1109$，这样猫猫共需要 $1+1+9+1+9$ 次操作把 $n$ 变为 $0$。/n/n数据规模与约定/nSubtask 0（13 pts）：$n≤99$。/n/nSubtask 1（13 pts）：$n=10^k$，$k$ 为自然数。/n/nSubtask 2（13 pts）：$n=10^k−1$，$k$ 为正整数。/n/nSubtask 3（13 pts）：$n≤999999$。/n/nSubtask 4（48 pts）：无特殊限制。/n/n对于所有数据，$1≤T≤3333$，$1≤n≤9999999999999(=10^{13}-1)$，毕竟猫猫最多一捆只有 $13$ 根雪糕嘛。/n/n算法1/n/n(贪心) $O(logn)$/n/n对于这类数字处理问题，用数位dp是一种很自然的想法。这道题目的特殊之处在于小老鼠可以改变某个位置上的数字，这使得我们在dp的过程中需要考虑到这个因素。/n/n首先考虑不考虑小老鼠的情况下，假设我们已经将前$i$位数字全部变成了$0$，现在考虑第$i+1$位数字$digit$。我们需要选择一种策略，使得猫猫的步数最少。如果$digit=0$，那么我们可以选择不操作，这样猫猫的步数不会变化。如果$digit=1$，那么我们可以选择不操作，或者将这个位置上的数字减$1$，这两种情况猫猫的步数都会加$1$。如果$digit>1$，那么我们只能将这个位置上的数字减$1$，这样猫猫的步数会加$1$。/n/n考虑到小老鼠可能会在某个位置上将原来的数字$x$修改成$y$。我们想要使得猫猫的步数最小，因此我们应该在修改后，尽可能多地将后面的数字变成$9$。如果前面的数字已经全部变成$0$，那么我们无论怎么修改，猫猫都需要将整个数字变成$0$，因此我们不需要考虑这种情况。/n/n代码实现中，我们可以先将数字$n$转成字符串，然后从左往右遍历，用一个变量$pre$表示前缀中已经变成$0$的数字的个数。如果当前数字$digit=0$且前缀长度小于字符串长度，说明这是一个前导$0$，因此我们需要将$pre$加一。否则，我们需要模拟上述的策略，考虑当前数字$digit$和修改后的数字$y$，然后更新前缀长度和猫猫的步数。/n/nC++ 代码