题解：CF331C3 The Great Julya Calendar

· · 题解

有一个朴素的 dp 是直接设 dp_i 表示把 i 删到 0 的最小次数，可以转移：dp_i=\min(dp_{i-d})+1，其中 d 存在于 i 的数位中。

进一步观察性质发现，dp 数组是递增的。

:::info[这个结论的简单说明] 设 q(i) 为 i 的最大数位的数，那么有 q(i-1)\ge q(i)-1（可以自己举几个例子验证），所以可以数学归纳法证明原式。 :::

也就是说转移方程变为了 dp_i=dp_{i-D}+1，其中 D 为 i 的最大数位，但是此时还是很难解决。不过看到 n\le 10^{18}，以及转移和数位有关，大方向是数位 dp 没错了。

数位 dp 通常从高到低考虑，每次考虑到一位时递归下一位的状态，完成转移并使得总状态数可以接受。我们按照这个方式来走的话，可以设 dp_{mx,n} 表示当前处理的数为 n，转化到 n 之前的数位最大值为 mx，使 n 变为 0 的最小操作次数。这样设计状态好像就可以按照我们的方式转移：设 n 除去最高位为 a，那么我们就可以往下递归 a，接下来我们可能会尝试向下递归 n-a（即把除了最高位都变成 0 的 n），但是这里没有办法转移了，仔细想想，我们好像还需要知道递归的 a 减完以后剩下了什么。于是把 dp 数组的值改成一个二元组，这样终于可以成功转移了。

:::warning[细节问题] 转移到最后，我们可能会转移到 n\le 9 的情况，这个时候根据数位 dp 的经验需要特判。但是还有一个地方需要注意，就是如果说遇到 2001 这样的数，我们向下递归，此时递归到了状态 mx=2,n=1，那么这个时候使用操作了以后得到的数就是 1-2=-1，但是不能舍弃它，因为这对应着 2001-2=1999。也就是说，我们的 dp 状态的第二维“减完了以后剩下什么”可能是一个负数。同时这也提醒我们注意一个细节，在最后特判 n\le 9 的时候，即使 n=0 也不一定步数为 0，他可能对应着类似 2000-2=1998 这种，所以只有 mx=n=0 的时候，步数才可以是 0。 :::

现在我们保证了做法的正确性，但是没有说明做法的复杂度是否合理。但是分析一下，从 n 的角度考虑，每次转移都会转移到什么样的数：

第一种状态的量级为 O(\log n)，而后面两种情况因为开头的个位数是根据读入的 n 可以确定的，所以变化的只有最后一位数，量级为 O(\alpha \log n)，其中 \alpha 为进制，这里为 10。最后因为状态还包含了一个 mx，所以总的状态数为 O(\alpha^2 \log n)。

实现的时候我们要用 map 对状态进行记录，可能会再填一个 log，但是采用哈希表就不会。这里还是实现前者。

#include<bits/stdc++.h>
#define int long long
#define pi pair<int,int>
using namespace std;
map<pi,pi>qwq;
int n;
pi dfs(int mx,int n){
    if(qwq.count({mx,n}))return qwq[{mx,n}];
    if(n<=9)return {n>0||mx>0,n-max(mx,n)};
    int hd=1;
    while(hd<=n/10)hd*=10;
    pi low=dfs(max(mx,n/hd),n%hd);
    pi hi=dfs(mx,n-n%hd+low.second);
    return qwq[{mx,n}]={low.first+hi.first,hi.second};
}
signed main(){
    cin>>n;
    cout<<dfs(0,n).first;
    return 0;
}