题目

Solution

首先，想要最优，我们必须每次都取各位数字中的最大值进行操作
其次，操作次数是单调的： f ( n ) > = f ( n − 1 ) f(n)>=f(n−1) f(n)>=f(n−1)
d f s ( n , m x ) dfs(n,mx) dfs(n,mx) 要把 n n n化为 0 0 0 ， m x mx mx 表示比数 n n n最高位还要高的位的最大值
f i r s t first first表示操作次数， s e c o n d second second 表示在将该部分变为 0 0 0的过程中，多余的部分（退位）

Code

#include<bits/stdc++.h> using namespace std; #define F first #define S second typedef long long ll; typedef pair<ll,int> pl; ll n; map<pl,pl>mp; pl dfs(ll n,int mx){ if (mp[pl(n,mx)].F) return mp[pl(n,mx)]; if (n<10) return pl(n || mx,max((ll)mx,n)-n); ll m=1; while (m<=n/10) m*=10; int p=n/m; m*=p; pl a=dfs(n-m,max(p,mx)),b=dfs(m-a.S,mx); return mp[pl(n,mx)]=pl(a.F+b.F,b.S); } int main(){ scanf("%lld",&n); printf("%lld",dfs(n,0).F); }