Untitled
unknown
c_cpp
4 years ago
1.1 kB
3
Indexable
#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; .... .*.. ...* *... **/
Editor is loading...