AcWing

题目中要求变换次数最小其实第一印象应该是贪心即我们每一次都去成各位中最大的那个数字。

但是这个想法很容易推翻。

因为你这次乘了一个最大的数很有可能导致在最后的结果每一位都比较小相反如果你这次乘了一个较小的数可能最后的结果中有一位很大。

也就是说你只能保证当前操作是最优的但是往后多看几步的话就不一定是最优的了。

枚举的过程中我们需要存储一下这个数字都有哪几位然后从大到小开始枚举这个操作属于剪枝优化中的搜索顺序优化。

另外我们还可以进行两次最优性剪枝。

即如果当前的操作次数已经大于我们之前算出来的答案了我们就不需要去进行后续的操作了直接舍去。

1的。

证明也很简单我们可以让每一位都是9再去乘1个9即使是这样最后的位数依旧是最多多1。

假设当前有cntcntcnt位操作次数是stepstepstep目标是nnn位那么我们还需要进行的最小操作次数是n−cntn-cntn−cnt。

那么最终总的操作次数一定是大于等于stepn−cntstepn-cntstepn−cnt的。

如果这个数是大于我们之前的最优解的话也可以直接舍去。

三、代码

{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();