ACM模版

描述

题解

这个题好难理解的说，看讨论区的题解感觉晕头转向的，但是懵懵懂懂的看懂了两点，一：记忆化搜索，二：划分为两部分搜索。但是我依然不知道从何下手，很头疼，于是找了找，找到了某大牛的题解，不得不吐槽，这么久以来，我从来没有见过哪个程序设计竞赛选手的语文水平能够让你感觉十分高。这语言表达能力也是局限的狠，稍微一复杂的问题，就很难描述清楚，说得乱七八糟的，或许是我理解能力低下？╮(╯▽╰)╭哎，心塞，但是实在是找不到更好的题解了……

在这里，我也无法保证能够讲清楚这个题，因为我并没有彻底理解，我只能做到把自己理解的部分进行一个大致的描述吧……

首先，先考虑一个问题，想要最优，我们必须每次都取各位数字中的最大值进行操作，这个是显而易见的，但是如果就酱紫暴力解，肯定是要 TLE 的，于是乎，我们应该可以证明，假如 f(n) 表示数字 n 化为 0 的操作次数，那么 f(n)>=f(n−1) ，这是单调不减的，所以呢，我们可以想明白为什么可以将 n 进行划分后搜索，因为他始终可以由某特定划分规则划分后，两部分操作次数之和来实现其化为 0 。

这时，我们设 dfs(mx,n) 表示把 n 化为 0 的最少操作次数，这里 mx 表示比数 n 最高位还要高的位的最大值，这里需要解释一下，除了递归入口时，n 就是最大的状态，其他深度的时候 n 都是由更大的一个数划分开来得到的一个位数比较小的 n ，所以呢，mx 实际上是表示前边已经划分掉处理完的部分的最大值。

好了，接下来也就是重点来了，怎么划分，这个部分在 51Nod 官方讨论区中已经说得很明显的，一个数，加入说是 1234 ，那么可以将其划分为 1000 和 0234 两部分，先处理后半部分，然后再处理前半部分，我们再递归时，需要返回一个 pll 数对，first 表示操作次数，second 表示在将该部分变为 0 的过程中，多余或者欠缺的部分，这里怎么讲呢？看代码 dfs 中当 n 小于 10 的时候，我们 second 等于所有位数的最大值减去此时的 n ，酱紫的话就会出现是否真的可以一下子完美变为 0 ，如果不能的话，一定会最后少若干，那么在我们处理完后半部分后，这少的部分可以由前半部分贡献。当然，这里说的长篇大论也是有些绕口的，拿个例子来说， 21 吧，如果划分的话会变为考虑 20 部分和 01 部分，此时，按照我们最开始的贪心思路，我们想要减去的话，一定是要减去 2 ，可是后半部分不够 2 ，那么我们可以从高位借，刚好此时我们递归返回的数对是 pll(1,1) ，说明我们欠一个，那么我们将要在 20 这部分减去这一个，那么也就变成了 19 了。总而言之，这部分就是不够就借。

此时，我想这道题已经分析的我自己都信了，但是并不算完，因为这个东西如果不记忆化的化，就会超时，因为肯定会有许许多多重复的状态，那么我们借用 map 离散化来做记忆化，因为数据范围实在是太大了……

实际上，这个题是一个树归题，很难！最起码我是想不起来这样子搞事情~~~如果哪里还有不懂的，可以讨论区一起交流一下下……

代码

#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

ll n;
map<pll, pll> mpp;

pll dfs(ll mx, ll n)
{
    if (mpp[pll(mx, n)].first)
    {
        return mpp[pll(mx, n)];
    }
    if (n < 10)
    {
        return pll(mx > 0 || n > 0, max(mx, n) - n);
    }

    ll m = 1;
    while (m <= n / 10)
    {
        m *= 10;
    }
    ll p = n / m;
    m = p * m;
    pll a = dfs(max(mx, p), n - m);
    pll b = dfs(mx, m - a.second);
    return mpp[pll(mx, n)] = pll(a.first + b.first, b.second);
}

int main()
{
    scanf("%lld", &n);
    printf("%lld\n", dfs(0, n).first);

    return 0;
}