fork download 
  1. //cop code
  2. #pragma GCC optimize("Ofast")
  3. #include <bits/stdc++.h>
  4. #define hutao_my_wife ios_base::sync_with_stdio(0);
  5. #define forcalors_so_cute cin.tie(0);
  6. #define ll long long
  7. #define int ll //這個int單純是因為debug時懶得找溢位的程式碼
  8. #define pii pair<int,int>
  9. #define ff first
  10. #define ss second
  11. #define pb push_back
  12. #define eb emplace_back
  13. #define bug(A) cout<<A<<" hi\n";
  14. using namespace std;
  15.  
  16. const int M = 200005;
  17. ll dp[20][10][10];
  18. ll to[20][10][10];
  19. int maxdigital(ll x){
  20.     ll ans = 0;
  21.     while(x){
  22.         ans = max(ans,x%10);
  23.         x/=10;
  24.     }
  25.     return ans;
  26. }
  27. int numi(ll x){
  28.     x/=10;
  29.     int ans = 0;
  30.     while(x%10 == 9){
  31.         ans++;
  32.         x/=10;
  33.     }
  34.     return ans;
  35. }
  36. void solve(){
  37.     ll n;
  38.     cin>>n;
  39.     ll ans = 0;
  40.     while(n>0){
  41.         int i = numi(n);
  42.         int k = maxdigital(n - n%(ll)pow(10,i+1));
  43.         int j = n%10;
  44.         ans += dp[i][j][k];
  45.         n -= (ll)pow(10,i+1);
  46.         n = n - n%10 + to[i][j][k];
  47.     }
  48.     cout<<ans<<'\n';
  49.  
  50. }
  51. signed main()
  52. {
  53.     hutao_my_wife forcalors_so_cute
  54.  
  55.     int t = 1;
  56.     memset(dp,0,sizeof(dp));
  57.     for(int i = 0; i <= 18; i++){
  58.         for(int k = 0; k < 10; k++){
  59.             for(int j = 0; j < 10; j++){
  60.                 if(i+j+k == 0){
  61.                     to[i][j][k] = 0;
  62.                     continue;
  63.                 }
  64.                 if(i+k == 0){
  65.                         dp[i][j][k]=1,to[i][j][k]=0;continue;
  66.                 }
  67.                 if(i == 0){
  68.                     if(j < k)dp[i][j][k] = 1,to[i][j][k]=(10+j-k)%10;
  69.                     else dp[i][j][k] = 2,to[i][j][k] = (10-k)%10;
  70.                     continue;
  71.                 }
  72.                 int last = j;
  73.                 for(int l = 9; l >= 0; l--){
  74.                     dp[i][j][k] += dp[i-1][last][max(k,l)];
  75.                     last = to[i-1][last][max(k,l)];
  76.                 }
  77.                 to[i][j][k] = last;
  78.             }
  79.         }
  80.     }
  81.     while(t--){
  82.         solve();
  83.     }
  84. }
  85.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
Standard input is empty
stdout 
93
https://ideone.com/P2OBvf
language:
C++14 (gcc 8.3)
created:
177 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!