fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. template<typename T>
  12. void minimize(T& a, const T& b) {
  13. if (b < a) a = b;
  14. }
  15.  
  16. const int N = 1e6 + 5;
  17.  
  18. int n;
  19. int dp[N]; // dp[i] = Số thao tác ít nhất để đưa i về 0
  20.  
  21. int main() {
  22. ios::sync_with_stdio(false);
  23. cin.tie(nullptr);
  24. cin >> n;
  25.  
  26. for (int i = 0; i <= n; i++) dp[i] = INF;
  27. dp[0] = 0;
  28.  
  29. for (int i = 1; i <= n; i++) {
  30. for (int tmp = i; tmp > 0; tmp /= 10) {
  31. int digit = tmp % 10;
  32. minimize(dp[i], dp[i - digit] + 1);
  33. }
  34. }
  35.  
  36. cout << dp[n];
  37. }
Success #stdin #stdout 0.01s 5288KB
stdin
27
stdout
5