用c++写这道题 题目描述 猫猫有若干个雪糕棒排成一排每个雪糕棒上有一个 0∼90∼9 的数字并且满足最左边的雪糕棒上写的数字不为 00。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 nn。 猫猫认为 00 是美好的所以她会尽可能把 nn 变成 00也就是把所有雪糕棒都拿走。 猫猫每次会进行一次操作。每次操作选择一个数字非 00 的雪糕棒并将其减 11。这之后如果最左边有连续的一些数字为 0

题目描述

猫猫有若干个雪糕棒排成一排，每个雪糕棒上有一个 $0\sim9$ 的数字，并且满足最左边的雪糕棒上写的数字不为 $0$。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 $n$。

猫猫认为 $0$ 是美好的，所以她会尽可能把 $n$ 变成 $0$，也就是把所有雪糕棒都拿走。

猫猫每次会进行一次操作。每次操作选择一个数字非 $0$ 的雪糕棒，并将其减 $1$。这之后，如果最左边有连续的一些数字为 $0$ 的雪糕棒（也即 $n$ 出现了前导 $0$），猫猫会把这些雪糕棒拿走。

小老鼠会来捣乱，它会在某个时刻（可能是所有操作开始之前，也可能是猫猫任意一次操作之后）改变某个雪糕棒上的一个数字。小老鼠总共只能改变一个数字。

小老鼠希望操作次数尽量多，猫猫希望操作次数尽量少，所以她想知道二者都使用最优策略时，她的操作次数。

输入格式 本题有多组数据。

第一行一个正整数 $T$ 表示数据组数。

对于每组数据：仅一行，一个正整数 $n$。

输出格式 共 $T$ 行，每行一个整数，表示答案。

输入输出样例 输入 #1

2 1100 11332132121

输出 #1

11 28

说明/提示 样例解释

对于第一组数据，小老鼠可以一开始就将 $1100$ 变为 $1109$，这样猫猫共需要 $1+1+9+1+9$ 次操作把 $n$ 变为 $0$。

数据规模与约定 Subtask 0（13 pts）：$n≤99$。

Subtask 1（13 pts）：$n=10^k$，$k$ 为自然数。

Subtask 2（13 pts）：$n=10^k−1$，$k$ 为正整数。

Subtask 3（13 pts）：$n≤999999$。

Subtask 4（48 pts）：无特殊限制。

对于所有数据，$1≤T≤3333$，$1≤n≤9999999999999(=10^{13}-1)$，毕竟猫猫最多一捆只有 $13$ 根雪糕嘛。

算法1

(贪心) $O(logn)$

对于这类数字处理问题，用数位dp是一种很自然的想法。这道题目的特殊之处在于小老鼠可以改变某个位置上的数字，这使得我们在dp的过程中需要考虑到这个因素。

首先考虑不考虑小老鼠的情况下，假设我们已经将前$i$位数字全部变成了$0$，现在考虑第$i+1$位数字$digit$。我们需要选择一种策略，使得猫猫的步数最少。如果$digit=0$，那么我们可以选择不操作，这样猫猫的步数不会变化。如果$digit=1$，那么我们可以选择不操作，或者将这个位置上的数字减$1$，这两种情况猫猫的步数都会加$1$。如果$digit>1$，那么我们只能将这个位置上的数字减$1$，这样猫猫的步数会加$1$。

考虑到小老鼠可能会在某个位置上将原来的数字$x$修改成$y$。我们想要使得猫猫的步数最小，因此我们应该在修改后，尽可能多地将后面的数字变成$9$。如果前面的数字已经全部变成$0$，那么我们无论怎么修改，猫猫都需要将整个数字变成$0$，因此我们不需要考虑这种情况。

代码实现中，我们可以先将数字$n$转成字符串，然后从左往右遍历，用一个变量$pre$表示前缀中已经变成$0$的数字的个数。如果当前数字$digit=0$且前缀长度小于字符串长度，说明这是一个前导$0$，因此我们需要将$pre$加一。否则，我们需要模拟上述的策略，考虑当前数字$digit$和修改后的数字$y$，然后更新前缀长度和猫猫的步数。

C++ 代