Участник:Novruzov.sb/Operators

Материал из DISCOPAL
< Участник:Novruzov.sb
Версия от 11:04, 20 ноября 2020; Novruzov.sb (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/least-operators-to-express-number/ С++ <code-cpp> class Solution { public: int leastOpsExpressTarget(int x, int target) {…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/least-operators-to-express-number/

С++

class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        init(x);
        return dp(target);
    }
 
    int dp(int target){
        if(mdp.count(target)) return mdp[target];
        auto it = mpow.lower_bound(target);
        auto pre = prev(it);
 
        auto [prepow, val] = *pre;
        int times = target/ prepow, res = target % prepow;
        int cnt = times * (val+1) - 1;
        if(res > 0) cnt += 1 + dp(res);
 
        int complement = it->first - target;
        if(complement < target){
            auto cnt2 = it->second + 1 + dp(it->first - target);
            cnt = min(cnt, cnt2);
        }
        return mdp[target] = cnt;
    }
 
    void init(int x){
        mpow[0] = 0;
        mpow[1] = 1;
        int cnt = 0;
        long long xpow = x;
        while(xpow < 1e11){
            mpow[xpow] = cnt++;
            xpow *= x;
        }        
        mdp.insert(mpow.begin(), mpow.end());
    }
 
    unordered_map<long long, int> mdp;
    map<long long, int> mpow;
};