题目描述

小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响：

• 小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc；
• 小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec。

现有 m 辆公交车，编号为 0 到 m-1。小扣也可以通过搭乘编号为 i 的公交车，从 x 号站点移动至 jump[i]*x 号站点，耗时仅为 cost[i]。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。

假定小扣起始站点记作 0，秋日市集站点记作 target，请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。

注意：小扣可在移动过程中到达编号大于 target 的站点。

样例

输入：target = 31, inc = 5, dec = 3, jump = [6], cost = [10]
输出：33
解释：
小扣步行至 1 号站点，花费时间为 5；
小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台，花费时间为 10；
小扣从 6 号站台步行至 5 号站台，花费时间为 3；
小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台，花费时间为 10；
小扣从 30 号站台步行至 31 号站台，花费时间为 5；
最终小扣花费总时间为 33。

输入：target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]
输出：26
解释：
小扣步行至 1 号站点，花费时间为 4；
小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台，花费时间为 4；
小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，花费时间为 3；
小扣从 33 号站台步行至 34 站台，花费时间为 4；
小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，花费时间为 4；
小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台，花费时间为 7；
最终小扣花费总时间为 26。

限制

• 1 <= target <= 10^9
• 1 <= jump.length, cost.length <= 10
• 2 <= jump[i] <= 10^6
• 1 <= inc, dec, cost[i] <= 10^6

算法

(记忆化搜索) $O(\log target)$

1. 分析一下有意义的转移点，对于当前的 target 来说，有两种转移方式
   • 直接从 0 走到 target
   • 搭乘一趟公交车到距离 target 最近的站点
2. 这里两种转移方式的原因是，如果搭乘公交车不如走路快，则就会一直走路。一旦发现搭乘公交车比走路快，那就尽可能的搭乘公交车。
3. 使用哈希表记录一下访问过的 target，加速转移。

时间复杂度

• 转移点大概有 $O(\log target)$ 个，每个转移点最多访问一次，故总时间复杂度为 $O(\log target)$。

空间复杂度

• 需要 $O(\log target)$ 的额外空间存储哈希表和系统栈。

C++ 代码

#define LL long long

class Solution {
private:
    unordered_map<int, LL> seen;

    LL solve(int target, int inc, int dec,
             const vector<int> &jump, const vector<int> &cost) {

        if (target == 0) return 0;
        if (seen.find(target) != seen.end()) return seen[target];

        const int m = jump.size();

        LL res = (LL)(target) * inc;
        for (int i = 0; i < m; i++) {
            int d = target / jump[i], r = target % jump[i];
            res = min(res, solve(d, inc, dec, jump, cost)
                            + cost[i] + (LL)(r) * inc);
            if (d+1 < target)
                res = min(res, solve(d+1, inc, dec, jump, cost) 
                                + cost[i] + (LL)(jump[i] - r) * dec);
        }

        return seen[target] = res;
    }

public:
    int busRapidTransit(int target, int inc, int dec,
                        vector<int>& jump, vector<int>& cost) {
        const int mod = 1000000007;
        return solve(target, inc, dec, jump, cost) % mod;
    }
};