Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- using namespace std;
- const int MOD = 1e9 + 7;
- const int INF = 2e9 + 10;
- const int maxn = 1e6 + 5;
- int n;
- int dp[maxn];
- int rec(int number) {
- if(number == 0) {
- return 0;
- }
- if(dp[number] != -1) {
- return dp[number];
- }
- int ret = INF;
- int tmp = number;
- while(tmp > 0) {
- int digit= tmp % 10;
- if(number - digit >= 0 and digit > 0)
- ret = min(ret, rec(number - digit) + 1);
- tmp /= 10;
- }
- dp[number] = ret;
- return ret;
- }
- int main(){
- cin >> n;
- for(int i = 0; i <= n; ++i) {
- dp[i] = -1;
- }
- cout << rec(n) << endl;
- }
- //869167734
- //869167734
Advertisement
Add Comment
Please, Sign In to add comment