Untitled

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
1.1 kB
0
Indexable
Never
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int MOD = 1000000007;
vector<int> pals;
int E;
int memo[100005];

int main()
{
    int S;
    cin >> S >> E;
    for(int i = 1; i <= 99999; i++) {
        memo[i] = 2000000;
        vector<int> v;
        int tmp = i;
        while(tmp > 0) {
            v.push_back(tmp % 10);
            tmp /= 10;
        }
        int L = 0, R = v.size() - 1;
        bool ok = true;
        while(L < R) {
            if(v[L] != v[R]) {
                ok = false;
                break;
            }
            L++;
            R--;
        }
        if(ok == true) {
            pals.push_back(i);
        }
    }
    memo[S] = 0;
    for(int sum = S; sum <= E; sum++) {
        for(int i = 0; i < pals.size(); i++) {
            if(pals[i] < sum and sum + pals[i] <= E) {
                memo[sum + pals[i]] = min(memo[sum + pals[i]], memo[sum] + 1);
            }
        }
    }
    cout << memo[E] << endl;
    return 0;
}
/*
 
 f(i, j) --> f(i, j + 1); f(i + 1, j)
 i == n - 1 && j == n - 1
 return 1;
 ....
 .*..
 ...*
 *...

 **/